邻值查找

AcWing-136-邻值查找

分析

见《进阶指南》第61页。

实现

#include <iostream>
#include <algorithm>
#include <stack>
#define inf 0x7fffffff
#define next NeXt
using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
struct element {
    int val, idx;
    bool operator < (const element& o) const {
        return val < o.val;
    }
};
int n, b[N];
element a[N];
stack<PII> s;

// ---------- 双向链表模板 ----------
struct Node {
    element data;
    int prev, next;
    #define data(x) node[x].data
    #define prev(x) node[x].prev
    #define NeXt(x) node[x].NeXt // NeXt
};
Node node[N];
int head, tail, idx;

void initialize () {
    head = 1, tail = 2, idx = 2;
    next(head) = tail;
    prev(tail) = head;
}
int insert (int ptr, element data) {
    int cur = ++ idx;
    data(cur) = data;

    prev(next(ptr)) = cur;
    next(cur) = next(ptr);

    next(ptr) = cur;
    prev(cur) = ptr;
    return cur;
}
void remove (int ptr) {
    next(prev(ptr)) = next(ptr);
    prev(next(ptr)) = prev(ptr);
}

int main () {
    initialize(); // 初始化链表
    int n;
    scanf("%d", &n);
    for (int i = 1, val; i <= n; ++ i) {
        scanf("%d", &val);
        a[i] = { val, i };
    }

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i)
        b[a[i].idx] = insert(prev(tail), a[i]);
    data(head).val = data(tail).val = inf; // 边界
    for (int i = n; i >= 2; -- i) {
        int ptr = b[i], res = inf, index;
        // ---------- 后继 ----------
        if (res > abs(data(next(ptr)).val - data(ptr).val)) {
            res = abs(data(next(ptr)).val - data(ptr).val);
            index = data(next(ptr)).idx;
        }
        // ---------- 前驱 ----------
        if (res >= abs(data(prev(ptr)).val - data(ptr).val)) {
            res = abs(data(prev(ptr)).val - data(ptr).val);
            index = data(prev(ptr)).idx;
        }
        remove(ptr);
        s.push({ res, index });
    }
    while (!s.empty()) {
        printf("%d %d\n", s.top().first, s.top().second);
        s.pop();
    }
    return 0;
}