题解：P10466 邻值查找

c______ · 2024-07-09 11:35:58 · 题解

提供一种双链表的做法：

思路

先将 A 数组排序，再用 B 数组，记录 A 中元素在双链表的位置。

为了后面的点对前面情况点答案计算无影响，采用倒序枚举每个点在链表的位置从 n 到 n - 2 ，计算左侧和右侧答案，比较大小，用 pair<int, int> 记录答案及位置，把该点删除计算再前一次。

最后输出答案即可。

时间复杂度 O(n\log n) ，瓶颈在排序.

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const ll INF = 2e18;

int n;
int l[N], r[N], b[N];
struct node
{
    ll val, id;
    bool operator< (const node &e) const
    {
        return val < e.val;
    }
}a[N];
pair<ll, ll> ans[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i].val;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n);
    a[0].val = -INF,a[n + 1].val = INF;
    for (int i = 1; i <= n; i ++)
    {
        l[i] = i - 1;
        r[i] = i + 1;
        b[a[i].id] = i;
    }
    for(int i = n; i >= 2; i --)
    {
        ll pos = b[i];
        ll lpos = l[pos], rpos = r[pos];
        ll lval = abs(a[pos].val - a[lpos].val);
        ll rval = abs(a[pos].val - a[rpos].val);
        if(lval <= rval)
            ans[i] = make_pair(lval, a[lpos].id);
        else
            ans[i] = make_pair(rval, a[rpos].id);
        r[lpos] = rpos;
        l[rpos] = lpos;
    }
    for (int i = 2; i <= n; i ++)
        cout << ans[i].first << " " << ans[i].second << endl;
    return 0;
}