邻值查找的一般解法有平衡树(STL set)和排序+双链表,复杂度均是$O(nlogn)$。
(当然还有权值线段树和单调栈+二分,但复杂度差不多,这里不详述)
其它用STL模拟链表的,都差不多是800+ms
可见数组模拟的复杂度还是足够优秀的,但还是跳不出$O(nlogn)$的范围。
想知道接近线性的复杂度怎么做吗?
算法
其实很容易,双链表算法的瓶颈在排序上,所以我们只需要一个更快的排序算法。
所以我们有了:
鸡排
基数排序
最近在看SA,就顺便介绍下这玩意。
基数排序可以看作桶排序的一种拓展,即设定一个基数b,在b进制下比较每个数的每位,从而达到高效排序的目的。
举个例子,有12个数:
13 23 34 27 19 37 43 22 11 9 21 40
在十进制下先按个位排序:
40 11 21 22 13 23 43 34 27 37 19 9
再按十位排序:
9 11 13 19 21 22 23 27 34 37 40 43
时间复杂度为$O((n+b)log_b(n))$。
在程序实现时,我们一般取b=256,同时用位运算处理,这样int范围内只要排4次即可。
需要注意的是,基数排序只适用于正数,负数可以通过偏移来处理。
//【蒟蒻】天依小柠檬(wyp)
//SH
const int INF=2e9;//开两倍,因为要比较差值
//cnt[k]记录排序时当前位为k的个数
//b缓存排序后的id
//id数组记录a[i]排序后处于哪个位置
inline void radix_sort(int id[],int n){//按编号基数排序
for(int i=1;i<=n;++i)a[i]+=INF>>1;//全部变成正数
for(int i=0;i<32;i+=8){
memset(cnt,0,sizeof(cnt));//计数器清零
for(int j=1;j<=n;++j)++cnt[(a[id[j]]>>i)&255];//a[j]当前位计数器++
for(int k=1;k<256;++k)cnt[k]+=cnt[k-1];//个数求前缀和(用来填下标)
for(int j=n;j;--j)b[cnt[(a[id[j]]>>i)&255]--]=id[j];//将排序后的id倒着放入b中,然后计数器--
for(int j=1;j<=n;++j)id[j]=b[j];//复制
}
for(int i=1;i<=n;++i)a[i]-=INF>>1;//还原
}
...
for(int i=1;i<=n;++i)scanf("%d",&a[id[i]=i]);
radix_sort(id,n);
这样就得到了优化后的效率。
下面这张是我用指针模拟的效率:
比数组稍微慢一点,但还能接受。
实现起来数组可能代码比较长,但容易调试,而且空间小一点
C++代码
指针版
//【蒟蒻】天依小柠檬(wyp)
//SH
struct Node{//双链表
int val,rk;//rk记录当前数值排序前处于哪个位置
Node *pre,*nxt;
};
Node *head,*tail,*q,*p[N];
//p[i]记录排名第i的值在链表中的地址
void init(){//初始化
head=new Node();
tail=new Node();
head->nxt=tail;
head->val=-INF;
tail->pre=head;
tail->val=INF;
}
void insert(Node *p,int val){//在p后插入值为val的新节点
q=new Node();
q->val=val;
p->nxt->pre=q;
q->pre=p;
q->nxt=p->nxt;
p->nxt=q;
}
void dele(Node *p){//删除p
p->pre->nxt=p->nxt;
p->nxt->pre=p->pre;
delete p;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)scanf("%d",&a[id[i]=i]);
radix_sort(id,n);
init();
for(int i=n;i>=1;--i){//将排序后数值依次插入链表
insert(head,a[id[i]]);p[id[i]]=head->nxt;head->nxt->rk=id[i];
}
for(int i=n;i>=2;--i){
int nowv=p[i]->val,prev=p[i]->pre->val,nxtv=p[i]->nxt->val;
//p[i]及其前驱、后继的值
if(nowv-prev<=nxtv-nowv)ans[i]=nowv-prev,pos[i]=p[i]->pre->rk;
else ans[i]=nxtv-nowv,pos[i]=p[i]->nxt->rk;
dele(p[i]);
}
for(int i=2;i<=n;++i)printf("%d %d\n",ans[i],pos[i]);
return 0;
}
参考资料
合并果子 加强版 题解
https://www.luogu.com.cn/blog/YCE-22/solution-p6038