136. 邻值查找

136. 邻值查找
给定一个长度为 n 的序列 A，A 中的数各不相同。
对于 A 中的每一个数 Ai，求：
min1≤j<i|Ai−Aj|
以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。
输入格式
第一行输入整数 n，代表序列长度。
第二行输入 n 个整数A1…An,代表序列的具体数值，数值之间用空格隔开。
输出格式
输出共 n−1 行，每行输出两个整数，数值之间用空格隔开。
分别表示当 i 取 2∼n 时，对应的 min1≤j<i|Ai−Aj| 和 Pi 的值。
数据范围
n≤105,|Ai|≤109
输入样例：
3
1 5 3
输出样例：
4 1
2 1

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e5+10;
int n;
int p[N],l[N],r[N];
PII a[N],ans[N];
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].first;
    a[i].second=i;
  }
  sort(a+1,a+n+1);
  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;//记下每个点在下标中的位置 
  }
  for(int i=n;i>=1;i--){
    int j=p[i],left=l[j],right=r[j];
    ll lv=abs(a[j].first-a[left].first);
    ll rv=abs(a[right].first-a[j].first);
    if(lv<=rv)ans[i]={lv,a[left].second};
    else ans[i]={rv,a[right].second};
    r[left]=right,l[right]=left;
  } 
  for(int i=2;i<=n;i++)
  cout<<ans[i].first<<' '<<ans[i].second<<endl;
  return 0;
}