Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?6182??Solved:?2396
[Submit][Status][Discuss]

Description

最近，阿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)。【任務描述】你得到了一年當中，領養者和被收養寵物到來收養所的情況，希望你計算所有收養了寵物的領養者的不滿意程度的總和。這一年初始時，收養所里面既沒有寵物，也沒有領養者。

Input

第一行為一個正整數n，n<=80000，表示一年當中來到收養所的寵物和領養者的總數。接下來的n行，按到來時間的先后順序描述了一年當中來到收養所的寵物和領養者的情況。每行有兩個正整數a, b，其中a=0表示寵物，a=1表示領養者，b表示寵物的特點值或是領養者希望領養寵物的特點值。（同一時間呆在收養所中的，要么全是寵物，要么全是領養者，這些寵物和領養者的個數不會超過10000個）

Output

僅有一個正整數，表示一年當中所有收養了寵物的領養者的不滿意程度的總和mod 1000000以后的結果。

Sample Input

5
0 2
0 4
1 3
1 2
1 5

Sample Output

3
(abs(3-2) + abs(2-4)=3，最后一個領養者沒有寵物可以領養)
題解： 　　平衡樹的操作就不扯了，關鍵是理解題意，人如果領不到寵物，可以等在寵物收養所中，直到有了寵物就可以馬上領養。所以我用了一個NOW記錄當前的平衡樹維護的是狗還是人。 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=80010; 4 const int MOD=1000000; 5 int root,tot,N,ANS; 6 int key[maxn],siz[maxn],lc[maxn],rc[maxn]; 7 int NOW=-1; 8 void r_rotate(int &rt){ 9 int k=lc[rt]; 10 lc[rt]=rc[k]; 11 rc[k]=rt; 12 siz[k]=siz[rt]; 13 siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 14 rt=k; 15 } 16 void l_rotate(int &rt){ 17 int k=rc[rt]; 18 rc[rt]=lc[k]; 19 lc[k]=rt; 20 siz[k]=siz[rt]; 21 siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 22 rt=k; 23 } 24 void MAINTAIN(int &rt,bool flag){ 25 if(flag==false){ 26 if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt); 27 else if(siz[rc[lc[rt]]]>siz[rc[rt]]){ 28 l_rotate(lc[rt]); 29 r_rotate(rt); 30 } 31 else return; 32 } 33 else{ 34 if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt); 35 else if(siz[lc[rc[rt]]]>siz[lc[rt]]){ 36 r_rotate(rc[rt]); 37 l_rotate(rt); 38 } 39 else return; 40 } 41 MAINTAIN(lc[rt],0); MAINTAIN(rc[rt],1); 42 MAINTAIN(rt,1); MAINTAIN(rt,0); 43 } 44 void insert(int &rt,int v){ 45 if(rt==0){ 46 rt=++tot; 47 key[rt]=v; 48 lc[rt]=rc[rt]=0; siz[rt]=1; 49 return ; 50 } 51 siz[rt]++; 52 if(v<=key[rt]) insert(lc[rt],v); 53 else insert(rc[rt],v); 54 MAINTAIN(rt,v>key[rt]); 55 } 56 int Delete(int &rt,int v){ 57 int ans; 58 siz[rt]--; 59 if(v==key[rt]||(v<key[rt]&&lc[rt]==0)||(v>key[rt]&&rc[rt]==0)){ 60 ans=key[rt]; 61 if(lc[rt]==0||rc[rt]==0) rt=lc[rt]+rc[rt]; 62 else key[rt]=Delete(lc[rt],key[rt]+1); 63 return ans; 64 } 65 if(v<key[rt]) ans=Delete(lc[rt],v); 66 else ans=Delete(rc[rt],v); 67 return ans; 68 } 69 bool find(int &rt,int v){ 70 if(rt==0) return false; 71 else if(v==key[rt]) return true; 72 else if(v<key[rt]) return find(lc[rt],v); 73 else if(v>key[rt]) return find(rc[rt],v); 74 } 75 int rank(int &rt,int v){ 76 if(rt==0) return 1; 77 if(v<=key[rt]) return rank(lc[rt],v); 78 else return siz[lc[rt]]+1+rank(rc[rt],v); 79 } 80 int select(int &rt,int k){ 81 if(k==siz[lc[rt]]+1) return key[rt]; 82 if(k<=siz[lc[rt]]) return select(lc[rt],k); 83 else return select(rc[rt],k-1-siz[lc[rt]]); 84 } 85 int pred(int &rt,int v){ 86 if(rt==0) 87 return v; 88 if(v<=key[rt]) 89 return pred(lc[rt],v); 90 else{ 91 int ans=pred(rc[rt],v); 92 if(ans==v) return key[rt]; 93 } 94 } 95 int succ(int &rt,int v){ 96 if(rt==0) return v; 97 if(v>=key[rt]) return succ(rc[rt],v); 98 else{ 99 int ans=succ(lc[rt],v); 100 if(ans==v) return key[rt]; 101 } 102 } 103 int main(){ 104 freopen("1.in","r",stdin); 105 freopen("1.out","w",stdout); 106 scanf("%d",&N); 107 for(int i=1,kin,num;i<=N;i++){ 108 scanf("%d%d",&kin,&num); 109 if(kin==0){//狗 110 if(NOW==-1){ NOW=0;insert(root,num); } 111 else if(NOW==0) insert(root,num); 112 else if(NOW==1){ 113 bool jud=find(root,num); 114 if(jud==true) Delete(root,num); 115 else{ 116 int tmp1=pred(root,num); int tmp2=succ(root,num); 117 if((find(root,tmp1)==true)&&(find(root,tmp2)==false||abs(num-tmp1)<=abs(num-tmp2))){ 118 ANS+=abs(num-tmp1)%MOD; 119 ANS%=MOD; 120 Delete(root,tmp1); 121 } 122 else if((find(root,tmp2)==true)&&((find(root,tmp1)==false)||abs(num-tmp1)>abs(num-tmp2))){ 123 ANS+=abs(num-tmp2)%MOD; 124 ANS%=MOD; 125 Delete(root,tmp2); 126 } 127 } 128 if(siz[root]==0) NOW=-1; 129 } 130 } 131 else{//人 132 if(NOW==-1){ NOW=1;insert(root,num); } 133 else if(NOW==1) insert(root,num); 134 else if(NOW==0){ 135 bool jud=find(root,num); 136 if(jud==true) Delete(root,num); 137 else{ 138 int tmp1=pred(root,num); int tmp2=succ(root,num); 139 if((find(root,tmp1)==true)&&(find(root,tmp2)==false||abs(num-tmp1)<=abs(num-tmp2))){ 140 ANS+=abs(num-tmp1)%MOD; 141 ANS%=MOD; 142 Delete(root,tmp1); 143 } 144 else if((find(root,tmp2)==true)&&((find(root,tmp1)==false)||abs(num-tmp1)>abs(num-tmp2))){ 145 ANS+=abs(num-tmp2)%MOD; 146 ANS%=MOD; 147 Delete(root,tmp2); 148 } 149 } 150 if(siz[root]==0) NOW=-1; 151 } 152 } 153 } 154 printf("%d",ANS); 155 return 0; 156 }

?

轉載于:https://www.cnblogs.com/CXCXCXC/p/5095092.html

總結

以上是生活随笔為你收集整理的bzoj1208: [HNOI2004]宠物收养所的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。