邻值查找
题意
给定一个长度为 n的序列 A ，A 中的数各不相同。
对于 A 中的每一个数 A i ，求：
m i n 1 ≤ j < i ∣ A i − A j ∣
以及令上式取到最小值的 j （记为 P i ）。若最小值点不唯一，则选择使 A j 较小的那个。
思路
将原数组按照权值递增排序后，构造成一个链表，然后按照输入顺序从后往前计算结果，每算出一个数 A i 的结果后，就将其从链表中删除，这样可以保证计算第 i 个数时，所有还存在的数在输入中一定在其前面 满足了题目要求的 1<=j<i
实现细节请看代码注释
代码
#include<bits/stdc++.h> #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1e5 + 10; int n; PII a[N]; // 记录每个数的权值和输入的下标 PII res[N]; // 记录答案 int p[N]; // 记录每个数排序后的下标 int l[N], r[N]; // 前向指针和后向指针数组 void solve() { cin >> n; rep(i, 1, n) { cin >> a[i].first; // 读入权值 a[i].second = i; // 记录下标 } sort(a + 1, a + 1 + n); // 按权值递增排序 rep(i, 1, n) { l[i] = i - 1; // 对排序后的数据构造链表 r[i] = i + 1; p[a[i].second] = i; // 记录排序前的下标对应的排序后的下标 } a[0].first = a[n + 1].first = LLONG_MAX; // 边界 for (int i = n; i > 1; --i) { // 按输入顺序从后往前计算答案 int j = p[i]; // j 表示第 i 个输入的数排序后在链表中的位置（下标） int left = l[j], right = r[j]; // 当前数在链表中的前驱节点和后继节点的下标 int v = a[j].first; // 当前节点的权值 int lv = abs(a[left].first - v); // 与左边节点的差的绝对值 int rv = abs(a[right].first - v); // 与右边节点的差的绝对值 if (lv <= rv) { // 如果当前数与 左边的数的差值 小于 与右边的数的插值 按照题目要求选择左边的数 res[i] = { lv,a[left].second }; // a[left].second 表示左边的数在原数组中的下标 } else { // 否则选择右边的点 res[i] = { rv,a[right].second }; } // 将当前节点从链表中删除 l[right] = left; r[left] = right; } // 按输入顺序输出答案 rep(i, 2, n) { printf("%lld %lld\n", res[i].first, res[i].second); } } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
