set中的查找操作

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