题解：P10466 邻值查找

形式化题意

给定一个长度为 $n$ 的序列 $A$，$A$ 中的数各不相同。

对于 $A$ 中的每一个数 $A_i$，求：

$\min_{1 \le j <i}|A_i-A_j|$

以及令上式取到最小值的 $j$（记为 $P_i$）。若最小值点不唯一，则选择使 $j$ 较小的那个。

本来就很简洁了。

做法

给大家推荐一个好 STL：std::set。

你只用理解成一个会自动给你排序，并且向前后移动指针都是 $\Theta(\log(n))$ 的容器就行了。

使用 s.find(a) 就是在 s 这个 set 里找到 a 这个元素，并返回它的指针（时间复杂度 $\Theta(\log(n))$）。

然后我们再比较它与前后的差异就可以了。

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
set<pii> s;
int n, a;
int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> a;
	s.insert(make_pair(a, 1));
	for (int i = 2; i <= n; ++i) {
		cin >> a;
		s.insert(make_pair(a, i));
		set<pii>::iterator t = s.find(make_pair(a, i));
		pii ans;
		ans.first = 1e9;
		if (++t != s.end()) {
			ans = make_pair(t->first - a, t->second);
		}
		--t;
		if (t-- != s.begin() && ans.first >= a - t->first) {
			ans = make_pair(a - t->first, t->second);
		}
		cout << ans.first << ' ' << ans.second << endl;
	}
	return 0;
}