本文主要是介绍CH 1301 邻值查找 set，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题 H: 邻值查找
时间限制: 1 Sec 内存限制: 128 MB
提交: 23 解决: 11
[提交] [状态] [讨论版] [命题人:admin]
题目描述
给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 Ai，求：
min(1≤j<i) |Ai-Aj|
以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。
输入
第一行一个整数n，第二行n个数A_1~A_n。
输出
n-1行，每行2个用空格隔开的整数。分别表示当i取2~n时，对应的 min(1≤j<i) |A_i-A_j| 和 P_i 的值。
样例输入
3
1 5 3
样例输出
4 1
2 1
提示
对于30%的数据: n<=100
对于70%的数据: n<=10^4
对于100%的数据: n<=10^5, |A_i|<=10^9
[提交][状态]
题意：求出每个数a之前的与a的差的绝对值最小的那个数，若差的绝对值相同，则输出数最小的那个
思路：STL里的set可以将输入的序列自动排序，那么就该数之前与之后的数字就是与该数差最小的数，比较之后输出即可
if else里面的条件改变了迭代器的位置，一直没发现，窒息
自认为写的挺麻烦，不过应该很好懂。。
代码：
#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;struct node {int val, pos;bool operator<(const node &rhs) const {return val < rhs.val;}
};set<node> p;int main() {int n, a, b;scanf("%d", &n);scanf("%d", &a);p.insert({a, 1});set<node>::iterator q, t;for (int i = 2; i <= n; i++) {scanf("%d", &b);p.insert({b, i});if (p.size() == 2) {printf("%d 1\n", abs(a - b));continue;}q = p.find({b, i});if ((++q) == p.end()) {q--;node x = (*(--q));x.val = abs(b - x.val);printf("%d %d\n", x.val, x.pos);continue;} else if ((--q) == p.begin()) {node x;x.val = abs(b - (*(++q)).val);x.pos = (*(q)).pos;printf("%d %d\n", x.val, x.pos);continue;}node x, y;q--;x.val = (*(q)).val;x.pos = (*q).pos;q++;y.val = (*(++q)).val;y.pos = (*(q)).pos;if (abs(b - x.val) < abs(b - y.val))printf("%d %d\n", abs(b - x.val), x.pos);else if (abs(b - x.val) > abs(b - y.val))printf("%d %d\n", abs(b - y.val), y.pos);else {printf("%d %d\n", abs(b - y.val), x.pos);}}return 0;
}
这篇关于CH 1301 邻值查找 set的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
