Yuzhen's Blog

Yuzhen Qin

题解:P10466 邻值查找

9
2024-06-17

题意

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

对于 A 中的每一个数 A_i,求:min_{1\le j<i}|A_i-A_j|

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

做法

对于 A_i 求出比它小的第一个数和比它大的第一个数(前驱和后继),选择差的绝对值小的一个。如果差的绝对值相等,选择在序列中靠前的一个。

可以使用 std::set 来存储序列,用 std::set::lower_bound()std::set::upper_bound() 查询前驱和后继。用一个 std::map 保存序列里值的位置。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	cin >> n;
	
	set<int> s;
	map<int, int> mp;
	
	int tmp;
	cin >> tmp;
	s.insert(tmp);
	mp[tmp] = 1;
	
	for(int i = 2; i <= n; i++) {
		cin >> tmp;
		
		s.insert(tmp);
		
		mp[tmp] = i;
		
		auto it_lower = s.lower_bound(tmp),
		     it_upper = s.upper_bound(tmp);
		
		int minval = 0x3f3f3f3f, pj = 0;
		
		if(it_lower != s.begin()) {
			--it_lower;
			// cout << *it_lower << endl;
			if(abs(tmp - *it_lower) < minval) {
				minval = abs(tmp - *it_lower);
				pj = mp[*it_lower];
			}
		}
		
		if(it_upper != s.end()) {
			// cout << *it_upper << endl;
			if(abs(tmp - *it_upper) < minval) {
				minval = abs(tmp - *it_upper);
				pj = mp[*it_upper];
			}
		}
		
		cout << minval << " " << pj << endl;
	}
	
	return 0;
}