CH1301 邻值查找【set应用】

1301 邻值查找 0x10「基本数据结构」例题

描述

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 A_i，求：
min(1≤j<i) ⁡|A_i-A_j|
以及令上式取到最小值的 j（记为 P_i）。若最小值点不唯一，则选择使 A_j 较小的那个。

输入格式

第一行一个整数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

思路：

用set或者是链表实现

读入第i个时，加入set，set中存的就是i之前的所有数，而且set是默认排好序的。

然后find找到i的位置，|Aj-Ai|最小的一定是Ai的前驱或者后继。

判断一下就行了。要注意Ai就是set的头或尾的情况。

奇怪的是，用printf输出的时候有一点问题不知道是为什么，用cout就行。

// ConsoleApplication2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


//#include "pch.h"
#include <iostream>
#include <set>
#include <cmath>
#include <stdio.h>
using namespace std;

int n;
const int maxn = 1e5 + 5;
struct node {
    int a;
    int id;
    bool operator < (const node &b)const {
        return a < b.a;
    }
}A[maxn];
set<node>sss;
set<node>::iterator after;
set<node>::iterator before;

int main()
{
    scanf("%d", &n);
    scanf("%d", &A[1].a);A[1].id = 1;
    sss.clear();
    sss.insert(A[1]);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &A[i].a);
        A[i].id = i;
        sss.insert(A[i]);
        after = sss.find(A[i]);
        before = sss.find(A[i]);
        //cout<<(*after).id<<endl;
        if (after == sss.begin()) {
            after++;
            cout<<abs((*after).a - A[i].a)<<" "<<(*after).id<<endl;
            //printf("%d %d
", abs((*after).a - A[i].a), (*after).id);
        }
        else if (after++, after == sss.end()) {
            before--;
            //node tmp = *before;
            //printf("%d
", tmp.a);
            cout<<abs((*before).a - A[i].a)<<" "<<(*before).id<<endl;
            //printf("%d %d
", abs((*before).a - A[i].a), (*before).id);
        }
        else {
            before--;
            if (abs((*before).a - A[i].a) < abs((*after).a - A[i].a)) {
                cout<<abs((*before).a - A[i].a)<<" "<<(*before).id<<endl;
            }
            else if(abs((*before).a - A[i].a) > abs((*after).a - A[i].a)){
                cout<<abs((*after).a - A[i].a)<<" "<<(*after).id<<endl;
            }
            else {
                if ((*before).a < (*after).a) {
                    cout<<abs((*before).a - A[i].a)<<" "<<(*before).id<<endl;
                }
                else {
                    cout<<abs((*after).a - A[i].a)<<" "<<(*after).id<<endl;
                }
            }
        }
    }
}