题目描述

给定一个长度为 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>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<ll,int>Pll;//ll可能爆Int
const int N=1e5+10;
Pll a[N],ans[N];//ans存放输出的两个值
int l[N],r[N],p[N];//p存放排序后的元素
int main()
{
    int n;
    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--)//从n开始逆序查找最小值
    {
        int j=p[i],left=l[j],right=r[j];
        ll left_value=abs(a[j].first-a[left].first);
        ll 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;
}