邻值查找

思路

我们发现，对于最后一个数字来说，它后面没有数字，所以这个数字的答案就是排序后它前面那个数字与它的差的绝对值。而在除去最后一个数字后，倒数第二个数字又成了新的最后一个数字，又可以用同样的方式计算答案。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e5+10;
pair<int,int> a[tt],ans[tt];
int l[tt],r[tt],p[tt];

signed main(){
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i].first;
		a[i].second=i;
	}
	sort(a+1,a+1+n);
	a[0].first-=2e9;
	a[n+1].first=2e9;
	for(int i=1;i<=n;i++){
		l[i]=i-1;
		r[i]=i+1;
		p[a[i].second]=i;
	}
	for(int i=n;i>1;i--){
		int j=p[i],left=l[j],right=r[j];
		int left_value=abs(a[j].first-a[left].first);
        int right_value=abs(a[j].first-a[right].first);
        if(left_value<=right_value){
        	ans[i]={left_value,a[left].second};
		}else{
			ans[i]={right_value,a[right].second};
		}
        l[right]=left,r[left]=right;
	}
	for(int i=2;i<=n;i++){
		cout <<ans[i].first<<" "<<ans[i].second<<endl;
	}
	return 0;
}

内存分配

待更新……

谢谢