题解|《算法竞赛进阶指南》 邻值查找

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

输入描述:
第一行一个整数n，第二行n个数A_1~A_n。

输出描述:
n-1行，每行2个用空格隔开的整数。分别表示当i取2~n时，对应的⁡|min(1≤j<i)⁡∣A_i −A_j|和P_i的值。

思路：
这是一道有关链表的题（此乃废话）。有多种解法，比如用STL中的set来做。但我们还是用链表来做吧，也不是很难。

时间复杂度分析：
因为需要用到sort（）所以大概是O(nlogn).

上代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 1000010;

int n;
PII a[N],ans[N];//一是值，二是下标
int p[N], l[N], r[N];//l[N]是左边的，r[N]是右边的

int main() {
    ios::sync_with_stdio;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a + 1, a + 1 + n);

    a[0].first = 1e9, a[n + 1].first = -1e9;//哨兵
    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];

        int lv = abs(a[left].first - a[j].first);
        int 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;