P05523. ycz的set
Description
pps就给你出了一道set入门题，他觉得你做出来了就代表你的set真正入门了。
由于pps太神了，所以你根本不敢反驳，只能老老实实地做出这题。而且pps表示，如果你不能在1s之内给出答案，pps将不会保你AK IOI
Format
Input
第一行为n，代表操作的个数
之后的n行，每行两个数opt,x
如果opt=1，那么请你在set中插入数x，如果数列中已经有x了，那么输出"orz pps,the number has appeared"
如果opt=2，那么请你在set中删除数x，如果数列中没有x，那么输出"orz pps,we don't have this number"
如果opt=3，那么请你输出在set中小于x的数的最大值，如果没有小于x的数，那么输出"orz pps,pps AK NOI"
如果opt=4，那么请你输出在set中大于x的数的最小值，如果没有大于x的数，那么输出"orz pps,pps AK IOI"
（输出orz时不需要输出引号）.
n<=1e5，x<=1e9
Output
对于每个询问操作，输出对应的答案
Samples
输入数据 1
10
1 5
1 2
2 3
1 8
3 8
4 2
1 9
1 5
2 9
4 9
输出数据 1
orz pps,we don't have this number
5
5
orz pps,the number has appeared
orz pps,pps AK IOI
Sol:此题考察学生对lower_bound(),upper_bound()相关操作的理解与变通
对于此类题，通常可在set中事先加入两个数字代表极小与极大值。
#include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;
set<int>s;
int main(){
int n;
scanf("%d",&n);
s.insert(inf);
s.insert(-inf);
while(n--)
{
int opt,x;
scanf("%d %d",&opt,&x);
if(opt==1)
{
if(s.count(x))
printf("orz pps,the number has appeared\n");
else
s.insert(x);
}
if(opt==2)
{
if(!s.count(x))
printf("orz pps,we don't have this number\n");
else
s.erase(s.lower_bound(x));
}
if(opt==3)
//在set中小于x的数的最大值
{
auto it=--s.lower_bound(x);
if(*it==-inf)
//找到的结果为-inf,说明是不存在的
printf("orz pps,pps AK NOI\n");
else
printf("%d\n",*it);
}
if(opt==4)
//输出在set中大于x的数的最小值
{
auto it=s.upper_bound(x);
if(*it==inf)
//找到的结果为inf,说明是不存在的
printf("orz pps,pps AK IOI\n");
else
printf("%d\n",*it);
}
}
return 0;
}
P01465. 邻值查找2
Description
输入一个数列。 就是每插入一个，找到前面插入过的与之差最小的值，将他们的差值加入答案
Format
Input
第一行为正整数N ，接下来的n行每行有一个正整数
N≤32767，每个数字≤1,000,000。
Output
如题
Samples
输入数据 1
6
5
1
2
5
4
6
输出数据 1
12
HINT 结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
Sol:此题与上一题类似，只是注意会涉及一些加减法操作，所以数据类型不要过界了
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int a[N];
set<int>s;
main()
{
int n,w;
long long sum=0;
cin>>n;
cin>>w;
s.insert(1<<30);
s.insert(-1<<30);
//这里用正负1<<30代表极大极小值
s.insert(w);
sum+=w;
for(int i=2;i<=n;i++)
{
int p;
cin>>p;
int x=*s.lower_bound(p);
int y=*(--s.lower_bound(p));
// cout<<"find it "<<x<<" "<<y<<endl;
// cout<<x-p<<" "<<p-y<<endl;
s.insert(p);
sum+=min((x-p),(p-y));
}
cout<<sum<<endl;
return 0;
}