算法竞赛进阶指南 CH1301邻值查找（set）

题目描述：

给定一个长度为 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≤10^5,|Ai|≤10^9

输入样例：

3
1 5 3
输出样例：

4 1
2 1

 

分析：

set的经典应用，可以找一个元素的前驱和后继，注意stl的find都为左闭右开的，如果it==s.end,则说明未找到。注意理解代码，有注释

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];
set<pair<int,int> >s;
pair<int,int> ans;
int main()
{

    int n;
    scanf("%d%d",&n,&a[1]);
    s.insert(make_pair(a[1],1));
    for(int i=2; i<=n; i++)
    {
        scanf("%d",&a[i]);
        s.insert(make_pair(a[i],i));

        set<pair<int,int> >::iterator it;
        it=s.find(make_pair(a[i],i));

        ans.first=1e9;
        if(++it!=s.end()) //it先++，在访问，看有没有后继
        {
            ans=make_pair(((*it).first)-a[i],(*it).second);
        }
        it=s.find(make_pair(a[i],i));
        
        if (it-- != s.begin() && ans.first >= a - (*it).first)//it是否为第一个，如果是先--
			ans = make_pair(a - (*it).first, (*it).second);
        
        /*if(it!=s.begin()) //这样也对
        {
            it--;
            if(ans.first>=a[i]-(*it).first)
                ans=make_pair(a[i]-(*it).first,(*it).second);
        }  */

        cout<<ans.first<<" "<<ans.second<<endl;
    }
    return 0;
}