题目描述
链接：https://ac.nowcoder.com/acm/contest/1007/A
来源：牛客网

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 A_i，求：
min(1≤j<i) |A_i-A_j|
以及令上式取到最小值的 j（记为 P_i）。若最小值点不唯一，则选择使 A_j 较小的那个。

分析
做任何一道题我们首先想到的肯定是暴力，然后再慢慢优化，这道题一看，如果我们直接暴力枚举一个一个找，时间复杂度为O(n*n),那必然超时,这个时候我们就自然而然想到了链表，首先我们需要用nlogn的时间复杂度去排个序，这样我们每次找都只需要找他的前驱和后继，因为这三个从小到大排序后相邻，差值必然比前面的小，然后我们每次询问，比较，删除都是O(1)的时间复杂度，忽略常数项，总的时间复杂度就是O(nlogn)，完美通过。
但除了链表，还有没有什么其他方法呢，当然有，那就是平衡树（STL set），同样的，我们只需要排好序后，查询前驱和后继就可以了，而二叉平衡树刚好就是一个支持动态插入，查询前驱，查询后继的数据结构。

理论有了，直接实践。

还有具体解释都在代码里了

链表

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

int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f; 
}
const int N=1e5+10;
int n;
struct data{
    int a,id,nex,pre;
}s[N];
int num[N];
int nod[N];
int ans[N];

bool cmp(const data &x,const data &y)
{
    if(x.a==y.a)
        return x.id<y.id;
    return x.a<y.a;
}

signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        s[i].a=read();
        s[i].id=i;
    }
    sort(s+1,s+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        s[i].pre=i-1;//前驱 
        s[i].nex=i+1;//后继 
        num[s[i].id]=i;//表示原序列中的a位于链表的哪一位置 
    }
    int k,fa,son;
    for(int i=n;i>=2;i--)//从后往前数，排除干扰 
    {
        k=num[i];//记录当前位置的编号 
        fa=s[k].pre;//前驱（比它小） 
        son=s[k].nex;//后继（比他大）
        //每计算一个数，就将这个数删去 
        s[fa].nex=son;//后继指针指向后一个 
        s[son].pre=fa;//前驱指针指向前一个
        //从逻辑上删去了s[k].a这个数 
        int p=s[son].a-s[k].a;//求与他最接近的两个数与他的差值 
        int q=abs(s[fa].a-s[k].a);
        if(son==n+1) p=0x3fffffff;//没有后继 
        if(fa==0) q=0x3fffffff;//没有前驱 
        if(p<q)
        {
            ans[i]=p;//选择差值小 
            nod[i]=s[son].id;
        }
        else if(p>q)
        {
            ans[i]=q;//选择差值小 
            nod[i]=s[fa].id;
        }
        else
        {
            ans[i]=q;
            nod[i]=s[fa].id;//选择序号小 
        }
    }
    for(int i=2;i<=n;i++)
        cout<<ans[i]<<" "<<nod[i]<<endl;
    return 0;

}

二叉平衡树

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

int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f; 
}

int n,a;
set<pair<int,int> > s;//第一个存数字，第二个存序号 

signed main()
{
    n=read();
    a=read();//先把第一个读进去，因为他不参与计算
    s.insert(make_pair(a,1));
    for(int i=2;i<=n;i++)
    {
        a=read();
        s.insert(make_pair(a,i));
        set<pair<int,int> >::iterator it=s.find(make_pair(a,i));//定义一个指针，查找他的序号
        pair<int,int> ans;//第一个存差值，第二个存序号 
        ans.first=0x7f7f7f7f;
        if(++it!=s.end())//如果他还有后继 
            ans=make_pair((*it).first-a,(*it).second);//他的后继减它本身 
        it=s.find(make_pair(a,i));//指针重置
        if(it--!=s.begin()&&ans.first>=a-(*it).first)//如果他还有前驱并且前驱的差值更小，选择更小的 
            ans=make_pair(a-(*it).first,(*it).second);
        cout<<ans.first<<" "<<ans.second<<endl; 
    } 
    return 0;
}

完美不！完美！撒花。