【链表】邻值查找
程序员文章站
2024-03-06 20:42:26
...
描述
给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 A_i,求:
min(1≤j<i) |A_i-A_j|
以及令上式取到最小值的 j(记为 P_i)。若最小值点不唯一,则选择使 A_j 较小的那个。
输入格式
第一行一个整数n,第二行n个数A_1~A_n。
输出格式
n-1行,每行2个用空格隔开的整数。分别表示当i取2~n时,对应的 min(1≤j<i) |A_i-A_j| 和 P_i 的值。
样例输入
3 1 5 3
样例输出
4 1 2 1
数据范围与约定
- 对于30%的数据: n<=100
- 对于70%的数据: n<=10^4
- 对于100%的数据: n<=10^5, |A_i|<=10^9
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct node { int value; int prev,next;//指针 }a[110000]; int head,tail,tot; int build()//新建链表 { tot=2; head=1;tail=2; a[head].next=tail; a[tail].prev=head; } int ins(int p,int val)//在p后插入包含数据val的新节点 { int q=++tot; a[q].value=val; a[a[p].next].prev=q;//p原来的下一个节点的上一个点改为q a[q].next=a[p].next;//q的下一个点改为p的下一个点 a[q].prev=p;//q的上一个点改为p a[p].next=q;//p的下一个点改为q } void remove(int p)//删除 { a[a[p].prev].next=a[p].next;//p的上一个点的下一个改为p的下一个点 a[a[p].next].prev=a[p].prev;//p的下一个点的上一个改为p的上一个点 } void clear()//数组模拟链表清空 { memset(a,0,sizeof(a)); head=tail=tot=0; } struct node2 { int x,id; }A[110000]; int cmp(const void*xx,const void*yy) { node2 n1=*(node2 *)xx; node2 n2=*(node2 *)yy; if(n1.x>n2.x) return 1; if(n1.x<n2.x) return -1; if(n1.x==n2.x) { if(n1.id>n2.id) return 1; if(n1.id<n2.id) return -1; } return 0; } int c[110000],s[110000]; int sum[110000],ans[110000]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i].x),A[i].id=i; qsort(A+1,n,sizeof(node2 ),cmp); build(); for(int i=1;i<=n;i++) { ins(tot,A[i].x); s[tot]=A[i].id; c[A[i].id]=tot; } memset(sum,0x3f,sizeof(sum)); memset(ans,0x3f,sizeof(ans)); for(int i=n;i>=1;i--) { int kk=a[c[i]].value; if(s[a[c[i]].prev]!=0) { sum[i]=abs(a[a[c[i]].prev].value-kk); ans[i]=s[a[c[i]].prev]; } if((sum[i]>abs(a[a[c[i]].next].value-kk))&&(s[a[c[i]].next]!=0)) { sum[i]=abs(a[a[c[i]].next].value-kk); ans[i]=s[a[c[i]].next]; } if((sum[i]==abs(a[a[c[i]].next].value-kk))&&(a[c[ans[i]]].value>a[a[c[i]].next].value)&&(s[a[c[i]].next]!=0)) { ans[i]=s[a[c[i]].next]; } remove(c[i]); } for(int i=2;i<=n;i++) printf("%d %d\n",sum[i],ans[i]); return 0; }
上一篇: PHP使用mysqli操作MySQL数据库的简单方法
下一篇: 邻值查找 链表实现