本题是找每个数左边的数和它的差绝对值的最小值,我们可以用pair储存每个数的值和它在原数组的位置,然后用链表存储排序后的值,从大到小枚举n保证每次枚举a[n].first的值都是原数组最右边的,因为链表已经排好序,这时只要比较它和前驱后驱的差的绝对值哪个较小即可,然后删除该节点保证每次都从最右的点开始。最后记得从小到大输出
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10,INF=1e8;
int p[N],l[N],r[N],n;
PII a[N],ans[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].first);
a[i].second=i;
}
sort(a+1,a+1+n);
a[0].first=-3e9,a[n+1].first=3e9;//处理边界
for(int i=1;i<=n;i++)
{
l[i]=i-1,r[i]=i+1;
p[a[i].second]=i;//存储a[i]现在的位置
}
for(int i=n;i>1;i--)
{
int j=p[i],left=l[j],right=r[j];
ll lt=abs(a[left].first-a[j].first);
ll rt=abs(a[right].first-a[j].first);
if(lt<=rt) ans[i]={lt,a[left].second};
else ans[i]={rt,a[right].second};
r[left]=right,l[right]=left;
}
for(int i=2;i<=n;i++)
printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}