关于重载运算符
重载运算符时,我们用了这种方法:
bool operator < (const node &x)const
{
return x.v<v;
}
实际上等同于这样
bool operator < (const node &x)const
{
return v > x.v;
}
也能写成这样的形式
friend const bool operator <(node x,node y){
return x.v>y.v;
}
我们会发现,这实际上是反过来的,有人给出的解释是这样的:
c++ STL 里面都是重载小于号,然后 STL 的优先队列默认是大根堆而不是小根堆,所以只能反着重载运算符
这个地方是要注意的
其实我们可以这样写:
friend const bool operator <(node y,node x){
return x.v<y.v;
}
一个指针占的空间 = 一个 long long 类型占的空间 = 8B。
我们可以以这种形式开数组
a=new int[n+5];
关于离散化
map<int,int>mpa;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
mpa[a[i]]=0;
}
for(map<int,int>::iterator it=mpa.begin();it!=mpa.end();it++)
it->second=++lena;
for(int i=1;i<=n;i++)
a[i]=mpa[a[i]];
时间复杂度\(O(nlogn)\)