「HNOI2004」宠物收养场

发表于 | 分类于 | | 浏览量： 次

set真香。

传送门

洛谷P2286

BZOJ1208

题解

只要记一下当前是人多还是宠物多，然后弄个平衡树维护一下。

每次找个前驱和后继，挑个接近的来。

也可以用STL里的set来维护。

然后注意一下细节就行了。

记得答案要取模。

代码

set真香

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<set>
#include<cstdio>
using namespace std;
int n,peo,pet,ans;set<int> S;set<int>::iterator p1,p2;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline int ABS(int x){return x<0?-x:x;}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		int opt=read(),a=read();
		if(opt==0)
		{
			if(peo==0){S.insert(a);pet++;}
			else
			{
				p1=p2=S.lower_bound(a);p2--;
				if(p1!=S.begin()&&(p1==S.end()||ABS(*p1-a)>=ABS(*p2-a))) p1--;
				ans+=ABS(*p1-a);
				S.erase(p1);peo--;
			}
		}
		else
		{
			if(pet==0){S.insert(a);peo++;}
			else
			{
				p1=p2=S.lower_bound(a);p2--;
				if(p1!=S.begin()&&(p1==S.end()||ABS(*p1-a)>=ABS(*p2-a))) p1--;
				ans+=ABS(*p1-a);
				S.erase(p1);pet--;
			}
		}
		ans%=1000000;
	}
	printf("%d\n",ans);
	return 0;
}