0x13 链表

邻值查找

给定一个长度为 的序列 ， 中的数各不相同。
对于 中的每一个数 ，求：

以及令上式取到最小值的 （记为 ）。若最小值点不唯一，则选择使 较小的那个。
输入格式
第一行输入整数 ，代表序列长度。
第二行输入 个整数,代表序列的具体数值，数值之间用空格隔开。
输出格式
输出共 行，每行输出两个整数，数值之间用空格隔开。
分别表示当 取 时，对应的 和 的值。
数据范围
,
输入样例：

3
1 5 3

输出样例：

4 1
2 1

该题可以用平衡树（STL set）求解，在这里我们讨论链表的做法。
把序列 A 从小到大排序，然后依次串成一个链表。注意在排序的同时，建立一个数组 B, 其中 表示原始序列中的 处于链表中的哪个位置（一个指针）。
因为链表有序，所以在链表中，指针 指向的节点 prev 和 next 就分别是 的前驱和后继。通过比较二者与 的差，我们就能求出与 最接近的值。
接下来，我们在链表中删除 $Bn$ 指向的节点，该操作复杂度 。
此时，我们按同样方法考虑  的 prev 和 next，再删除 。
以此类推，最终即可求出每个 最接近的值。
该解法的时间复杂度为 。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct rec{
    int val, pos;
}a[N];
int b[N], l[N], r[N];
int res[N], p[N];
bool cmp(rec x, rec y){
    return x.val < y.val;
}
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i].val);
        a[i].pos = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    for(int i=1;i<=n;i++) {
        b[a[i].pos] = i;        
    }
    for(int i=1;i<=n;i++){
        l[i] = i-1; r[i] = i + 1;
    }
    l[1] = 0, r[n] = 0;
    for(int i=n;i>=2;i--){
        int pos = b[i];
        if(l[pos] && r[pos]) {
            int lval = a[l[pos]].val;
            int rval = a[r[pos]].val;
            if(abs(lval - a[pos].val) <= abs(rval - a[pos].val)){
                res[i] = abs(lval - a[pos].val);
                p[i] = a[l[pos]].pos;
            } else {
                res[i] = abs(rval - a[pos].val);
                p[i] = a[r[pos]].pos;
            }
        } else if(l[pos]) {
            res[i] = abs(a[l[pos]].val - a[pos].val);
            p[i] = a[l[pos]].pos;
        } else {
            res[i] = abs(a[r[pos]].val - a[pos].val);
            p[i] = a[r[pos]].pos;
        }
        r[l[pos]] = r[pos];
        l[r[pos]] = l[pos];
    }    
    for(int i=2;i<=n;i++){
        printf("%d %d\n", res[i], p[i]);
    }
    return 0;
}