题目大意:
宠物收养所中每个宠物和人都有一个权值。一开始宠物收养所中没有东西。按顺序加入一些人和宠物。按照如下的规则进行收养:
1.若人来时没有宠物,则原地等待;
2.若人来时有宠物,则选择权值最接近的宠物中权值最小的宠物进行收养,代价为两者权值差;
3.若宠物来时有人,那么分配给权值最接近的人中权值最小的人收养,代价为两者权值差。
思路:
维护两棵平衡树,每次看一下对应的树中有没有结点。如果有,选择合适的计算代价,并从树上移除;如果没有,就将当前权值加入到另一棵树中。这显然可以用std::set维护。
1 #include<set>
2 #include<cstdio>
3 #include<cctype>
4 #include<climits>
5 inline int getint() {
6 register char ch;
7 while(!isdigit(ch=getchar()));
8 register int x=ch^'0';
9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
10 return x;
11 }
12 const int mod=1000000;
13 std::set<int> s[2];
14 int main() {
15 s[0].insert(INT_MIN);
16 s[0].insert(INT_MAX);
17 s[1].insert(INT_MIN);
18 s[1].insert(INT_MAX);
19 int ans=0;
20 for(register int i=getint();i;i--) {
21 const int opt=getint(),x=getint();
22 if(s[opt].size()==2) {
23 s[opt^1].insert(x);
24 continue;
25 }
26 const int l=*--s[opt].lower_bound(x);
27 const int r=*s[opt].lower_bound(x);
28 if(l==INT_MIN||(r!=INT_MAX&&x-l>r-x)) {
29 s[opt].erase(r);
30 ans+=r-x;
31 }
32 if(r==INT_MAX||(l!=INT_MIN&&x-l<=r-x)) {
33 s[opt].erase(l);
34 ans+=x-l;
35 }
36 ans%=mod;
37 }
38 printf("%d\n",ans);
39 return 0;
40 }
转载于:https://www.cnblogs.com/skylee03/p/8454419.html