欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CH 1301 邻值查找 set

程序员文章站 2024-03-06 20:59:20
...

问题 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;
}