题目描述

找到序列中某数的前一个数，使得该两数差值最小，且下标最小

返回对于每个数的最小差值和另一数的最小下标

题目分析

#include<algorithm>

lower_bound(x) 找到大于等于x的最小的数

upper_bound(x) 找到大于x的最小的数

返回值为iterator

所以可以利用upper_bound($A_i$) 找到大于$A_i$的最小的数

同时返回迭代器it–即为小于$A_i$的最大的数

然后对两数和$A_i$的差值进行比较，找到最小的差值

代码示例

#include<iostream>
#include<algorithm>
#include<set>
#include<limits.h>

using namespace std;

typedef long long LL;

int main()
{
    int n;
    set<pair<int, int>> s; //pair用于存储每个数值和其下标
    s.insert({INT_MIN, 0}); //加入哨兵，方便判断边界，可能出现该数是序列中最大值，返回迭代器为end
    s.insert({INT_MAX, 0});
    cin>>n;

    for(int i = 1; i <= n; i++)
    {
        int v;
        cin>>v;
        if(i > 1)
        {
            auto it = s.upper_bound({v, 0}); //由于只是用v值查找，所以下标任意
            auto nt = it; //找到大于v的最小的数
            nt--; //因为序列中的数各不相同，所以nt--即为小于v值的最大的数
            LL rv = it -> first - (LL)v, lv = (LL)v - nt -> first;
            //如果差值相同，返回Aj较小的那个，即小于v的那个数
            if(lv <= rv) cout<<lv<<' '<<nt -> second<<endl;
            else cout<<rv<<' '<<it -> second<<endl;
        }
        s.insert({v, i}); //插入该数
    }

    return 0;
}