邻值查找

当需要同时保存索引和值的时候，可以通过定义pair来处理

typedef pair<int, int> PII;

AC代码如下

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef long long LL;
typedef pair<LL, int> PII;

int n;
int p[N], l[N], r[N];
PII a[N], ans[N];

int main(void)
{
    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 = -3e9 - 1, a[n+1].first = 3e9 + 1;
    for (int i = 1; i <= n; i++) {
        l[i] = i - 1, r[i] = i + 1;
        p[a[i].second] = i; // 第i个插入的节点在双链表中的索引
    }

    for (int i = n; i > 1; i--) {
        int j = p[i], left = l[j], right = r[j];
        LL left_value = abs(a[left].first - a[j].first);
        LL right_value = abs(a[right].first - a[j].first);
        if (left_value <= right_value) ans[i] = {left_value, a[left].second};
        else ans[i] = {right_value, a[right].second};
        l[right] = left, r[left] = right;
    }

    for (int i = 2; i <= n; i++) {
        cout << ans[i].first << ' ' << ans[i].second << endl;
    }

    return 0;
}