利用C++标准库里的list 不用手写链表 懒人福音

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node {
    int v, p;
    bool operator < (const Node &a) const {
        return v < a.v;
    }
};
typedef list<Node> :: iterator it;
it b[N];
int main() {
    int n; cin >> n;
    list<Node>ls;
    for (int i = 1; i <= n; i++) {
        int a; scanf("%d", &a);
        ls.push_back((Node){a, i});
    }
    ls.sort();
    for (it i = ls.begin(); i != ls.end(); ++i) {
        b[i -> p] = i;
    }
    vector<Node>ans;
    ls.insert(ls.begin(), (Node){0, 0});
    for (int i = n; i >= 2; i--) {
        int k = 0x7f7f7f7f, p = 0x7f7f7f7f;
        it a = b[i];
        if (--a != ls.begin()) {
            int v = abs(b[i] -> v - a -> v);
            if (k > v) {
                k = v; p = a -> p;
            }
        }
        a = b[i];
        if (++a != ls.end()) {
            int v = abs(b[i] -> v - a -> v);
            if (k > v || k == v && a -> v < b[i] -> v) {
                k = v; p = a -> p;
            }           
        }
        ans.push_back((Node){k, p});
        ls.erase(b[i]);
    }
    for (int i = ans.size() - 1; i >= 0; i--) printf("%d %d\n", ans[i].v, ans[i].p);
}