[平衡樹]HNOI2004 寵物收養所 pet

題目描述

最近，阿Q開了一間寵物收養所。收養所提供兩種服務：收養被主人遺棄的寵物和讓新的主人領養這些寵物。每個領養者都希望領養到自己滿意的寵物，阿Q根據領養者的要求通過他自己發明的一個特殊的公式，得出該領養者希望領養的寵物的特點值a（a是一個正整數，a<2^31），而他也給每個處在收養所的寵物一個特點值。這樣他就能夠很方便的處理整個領養寵物的過程了，寵物收養所總是會有兩種情況發生：被遺棄的寵物過多或者是想要收養寵物的人太多，而寵物太少。

1．被遺棄的寵物過多時，假若到來一個領養者，這個領養者希望領養的寵物的特點值爲a，那麼它將會領養一隻目前未被領養的寵物中特點值最接近a的一隻寵物。（任何兩隻寵物的特點值都不可能是相同的，任何兩個領養者的希望領養寵物的特點值也不可能是一樣的）如果有兩隻滿足要求的寵物，即存在兩隻寵物他們的特點值分別爲a-b和a+b，那麼領養者將會領養特點值爲a-b的那隻寵物。
2．收養寵物的人過多，假若到來一只被收養的寵物，那麼哪個領養者能夠領養它呢？能夠領養它的領養者，是那個希望被領養寵物的特點值最接近該寵物特點值的領養者，如果該寵物的特點值爲a，存在兩個領養者他們希望領養寵物的特點值分別爲a-b和a+b，那麼特點值爲a-b的那個領養者將成功領養該寵物。

一個領養者領養了一個特點值爲a的寵物，而它本身希望領養的寵物的特點值爲b，那麼這個領養者的不滿意程度爲abs(a-b)。



【任務描述】
你得到了一年當中，領養者和被收養寵物到來收養所的情況，希望你計算所有收養了寵物的領養者的不滿意程度的總和。這一年初始時，收養所裏面既沒有寵物，也沒有領養者。
【輸入格式】
你將從文件當中讀入資料。文件的第一行爲一個正整數n，n<=80000，表示一年當中來到收養所的寵物和領養者的總數。接下來的n行，按到來時間的先後順序描述了一年當中來到收養所的寵物和領養者的情況。每行有兩個正整數a, b，其中a=0表示寵物，a=1表示領養者，b表示寵物的特點值或是領養者希望領養寵物的特點值。（同一時間呆在收養所中的，要麼全是寵物，要麼全是領養者，這些寵物和領養者的個數不會超過10000個）
【輸入樣例】
5
0 2
0 4
1 3
1 2
1 5
【輸出格式】
輸出文件中僅有一個正整數，表示一年當中所有收養了寵物的領養者的不滿意程度的總和mod 1000000以後的結果。
【輸出樣例】
3
(abs(3-2) + abs(2-4)=3，最後一個領養者沒有寵物可以領養)
【運行限制】
       運行時限：1秒鐘
【評分方法】
本題目一共有十個測試點，每個測試點的分數爲總分數的10%。對於每個測試點來說，如果你給出的答案正確，那麼你將得到該測試點全部的分數，否則得0分。

【分析】

平衡樹的基礎練習題，哦不，STL Set的基礎練習題！

直接使用C++ STL Set容器，建立兩個容器，分別是領養人和寵物，然後按照題目要求去『模擬』即可。

用到的Set函數：

1. 插入函數 

void insert(type x)

2. 查找函數  

set::iterator lower_bound(type x) 返回第一個>=x的元素的迭代器

3. 刪除函數 void erase(set::iterator iter)

=============================================

爲了防止意外，我使用了『同餘原理』，防止ans超過2^31。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25467

01 /*
02 *Problem: 寵物收養所 pet
03 *Author: Yee-fan Zhu
04 *Website: http://zhuyf.tk/
05 *Method: Balanced Tree
06          C++ Standard Templates Library: Set Container
07 *Cost: Total 310ms
08 *Memory: 499KB
09 */
10 #include <cstdio>
11 #include <cstdlib>
12 #include <set>
13 #include <iterator>
14 using namespace std;
15 typedef set<int>  Set;
16
17 const int MOD=1000000;
18 int N;
19 Set Pet,Owner;
20
21 int abs(int x)
22 {return x>0?x:-x;}
23
24 int Maintenance(Set& A,Set& B,int m)
25 {
26     int res=0;
27     if(A.size()==0)
28     {
29         B.insert(m);
30         return 0;
31     }
32     Set::iterator iter;
33     iter=A.lower_bound(m);
34     if(iter==A.end())
35     {
36         iter--;
37         res=abs(*iter-m);
38         A.erase(iter);
39         return res;
40     }
41     if(*iter==m)
42     {
43         A.erase(iter);
44         return 0;
45     }
46     if(iter==A.begin())
47     {
48         res=abs(*iter-m);
49         A.erase(iter);
50         return res;
51     }
52     Set::iterator tmp;
53     res=abs(*iter-m);
54     tmp=iter;
55    
56     iter--;
57     if(abs(*iter-m)<=res)
58     {
59         res=abs(*iter-m);
60         tmp=iter;
61     }
62     A.erase(tmp);
63     return res;
64 }
65
66 void init()
67 {
68     int Ans=0;
69     scanf("%d\n",&N);
70     int x,m;
71     for(int i=1;i<=N;i++)
72     {
73         scanf("%d %d\n",&x,&m);
74         if(!x)
75             Ans+=Maintenance(Owner,Pet,m);
76         else
77             Ans+=Maintenance(Pet,Owner,m);
78         Ans%=MOD;
79     }   
80     printf("%d\n",Ans);
81 }
82
83 int main()
84 {
85     freopen("pet.in","r",stdin);
86     freopen("pet.out","w",stdout);
87     init();
88     return 0;
89 }