【STL::set】CH1301 邻值查找(迭代器使用学习)

描述
给定一个长度为 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,因为set是有序集合,直接依次插入,每次找比这个数大的和小的,比较一下做差的绝对值。

  • 迭代器的使用:
  • set的迭代器只支持++和–两种运算
  • it++ 和 ++it 是不一样的,前者先返回自己,再运算,后者是先运算再返回自己。在使用的时候需要注意。
  • *号解除引用,*(it++) 和 *(++it)也是不一样的。尽管有括号。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
map<int,int> hm;
set<int> st;
int n;
int k[maxn]={0};
int main()
{
    scanf("%d",&n);
    scanf("%d",&k[1]);
    st.insert(k[1]);
    hm[k[1]]=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&k[i]);
        st.insert(k[i]);
        hm[k[i]]=i;
        set<int>::iterator it=st.find(k[i]),il=it;il++;
        if(it==st.begin())
        {
            int p1=*(++it);
            printf("%d %d\n",abs(k[i]-p1),hm[p1]);
        }
        else if(il==st.end())
        {
            int p2=*(--it);
            printf("%d %d\n",abs(k[i]-p2),hm[p2]);
        }
        else
        {
            int p1=*il;
            int p2=*(--it);
            if(abs(k[i]-p2)>abs(k[i]-p1))
            {
                printf("%d %d\n",abs(k[i]-p1),hm[p1]);
            }
            else
            {
                printf("%d %d\n",abs(k[i]-p2),hm[p2]);
            }
        }
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注