题目传送门
【题目大意】
给定一串长度为$n$的序列$A$，求对于$i\in [2,n]$，$min\{|A_i-A_j|\}(1\le j<i)$以及取得最小值时$j$的值。
【思路分析】
这道题可以用set做，一边插入一边排序，由于整个序列在set中是单调递增的，所以使得差最小的$A_j$在set中一定为$A_i$的前驱或者后继，可以直接用set自带的函数查询。
【代码实现】
1 #include<bits/stdc++.h> 2 #define rg register 3 #define go(i,a,b) for(rg int i=a;i<=b;i++) 4 using namespace std; 5 struct node{ 6 int num,id; 7 bool operator<(const node &t) const { 8 return num<t.num; 9 } 10 }; 11 set<node> a; 12 int main(){ 13 int n,x,y; 14 scanf("%d%d",&n,&x); 15 a.insert({x,1}); 16 set<node>::iterator q,t; 17 go(i,2,n){ 18 scanf("%d",&y); 19 a.insert({y,i}); 20 if(a.size()==2){ 21 printf("%d 1\n",abs(x-y)); 22 continue; 23 } 24 q=a.find({y,i}); 25 if((++q)==a.end()){ 26 q--;node z=(*(--q)); 27 z.num=abs(y-z.num); 28 printf("%d %d\n",z.num,z.id); 29 continue; 30 }else if((--q)==a.begin()){ 31 node z; 32 z.num=abs(y-(*(++q)).num); 33 z.id=(*(q)).id; 34 printf("%d %d\n",z.num,z.id); 35 continue; 36 } 37 node s1,s2; 38 q--; 39 s1.num=(*q).num; 40 s1.id=(*q).id; 41 q++;q++; 42 s2.num=(*q).num; 43 s2.id=(*q).id; 44 if(abs(y-s1.num)<=abs(y-s2.num)) 45 printf("%d %d\n",abs(y-s1.num),s1.id); 46 else printf("%d %d\n",abs(y-s2.num),s2.id); 47 } 48 return 0; 49 } 代码戳这里
转载于:https://www.cnblogs.com/THWZF/p/11234314.html
相关资源：BA 简实模板