AcWing 136 邻值查找(链表)

题目链接

解题思路

  如果将所有数字按从大到小排序，并且从编号最大的数开始找的话，那么他的左右两边的数肯定就是离他最近的数，计算之后把编号最大的数删掉，那么编号次大的数相当于之前编号最大的数...所以利用链表来做到O(1)删除，就能在O(nlogn)的时间内解题。

代码

const int maxn = 1e5+10;
P a[maxn], ans[maxn];
int p[maxn];
struct NODE {
    int l,r;
} chain[maxn];
int main() {
    int n; scanf("%d",&n);
    for (int i = 1; i<=n; ++i) {
        scanf("%lld",&a[i].first);
        a[i].second = i;
    }
    sort(a+1,a+n+1);
    a[0] = {-3e9,0}, a[n+1] = {3e9,n+1};
    for (int i = 1; i<=n; ++i) {
        chain[i] = {i-1,i+1};
        p[a[i].second] = i;
    }
    for (int i = n; i>1; --i) {
        int pos = p[i], left = chain[pos].l, right = chain[pos].r;
        ll v_l = a[pos].first-a[left].first, v_r = a[right].first-a[pos].first ;
        if (v_l<=v_r) ans[i] = {v_l,a[left].second};
        else ans[i] = {v_r,a[right].second};
        chain[left].r = right, chain[right].l = left;
    }
    for (int i = 2; i<=n; ++i) printf("%d %d
",ans[i].first, ans[i].second);
    return 0;
}