这东西我还是有点会玩的啊。。

邻值查找这东西不就是维护个前驱后继嘛。。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std; struct node
{
int x,id;
}a[];
bool cmp(node n1,node n2){return n1.x<n2.x;}
int p[];
int bef[],aft[];
int as[],pr[];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i].x), a[i].id=i;
sort(a+,a+n+,cmp); for(int i=;i<=n;i++)p[a[i].id]=i,bef[i]=i-,aft[i]=i+; for(int i=n;i>=;i--)
{
int t=p[i];as[i]=;
if(bef[t]!=)
{
int d=abs(a[t].x-a[bef[t]].x);
if(d<as[i])
as[i]=d, pr[i]=a[bef[t]].id;
}
if(aft[t]!=n+)
{
int d=abs(a[t].x-a[aft[t]].x);
if(d<as[i])
as[i]=d, pr[i]=a[aft[t]].id;
}
aft[bef[t]]=aft[t];
bef[aft[t]]=bef[t];
} for(int i=;i<=n;i++)printf("%d %d\n",as[i],pr[i]);
return ;
}

邻值查找

好的结果今天看一看下一题就是running median心态崩了,昨天才和苏大佬和林肯口胡了这题的链表做法。。。不做了。。。简直莫名其妙。。。

邻接表。。。还有人不会,吗。。。

05-11 22:24
查看更多