1208: [HNOI2004]寵物收養所 Time Limit: 10 Sec Memory Limit: 162 MB 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，最后一個領養者沒有寵物可以領養)
/*splay delete操作.*/#include<iostream>#include<cstdio>#define MAXN 80001#define mod 1000000#define INF 1e9using namespace std;int n,m,tree[MAXN][2],root,t1,t2,size,ans,fa[MAXN],s[MAXN],x1,x2;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void rotate(int x,int &k){ int y=fa[x],z=fa[y],l,r; if(tree[y][0]==x) l=0;else l=1;r=l^1; if(y==k) k=x; else { if(tree[z][0]==y) tree[z][0]=x; else tree[z][1]=x; } fa[x]=z,fa[y]=x,fa[tree[x][r]]=y; tree[y][l]=tree[x][r];tree[x][r]=y; return ;}void splay(int x,int &k){ int y,z; while(x!=k) { y=fa[x],z=fa[y]; if(y!=k){ if((tree[z][0]==y)^(tree[y][0]==x)) rotate(x,k); else rotate(y,k); } rotate(x,k); } return ;}void add(int &k,int x,int f){ if(!k){k=++size;s[size]=x;fa[k]=f;splay(k,root);return ;} if(x<s[k]) add(tree[k][0],x,k); else add(tree[k][1],x,k); return ;}void dele(int x){ splay(x,root);//轉根. if(!tree[x][0]) root=tree[x][1]; else if(!tree[x][1]) root=tree[x][0]; else {//找x的后繼,將左子樹嫁接到后繼上. int k=tree[x][1]; while(tree[k][0]) k=tree[k][0]; tree[k][0]=tree[x][0];fa[tree[x][0]]=k; root=tree[x][1]; } fa[root]=0; return ;}void before(int k,int x){ if(!k) return ; if(x>=s[k]){t1=s[k];x1=k;before(tree[k][1],x);return ;} else before(tree[k][0],x); return ;}void after(int k,int x){ if(!k) return ; if(x<=s[k]){t2=s[k];x2=k;after(tree[k][0],x);return ;} else after(tree[k][1],x); return ;}int main(){ int x,k,last; n=read(); for(int i=1;i<=n;i++) { k=read();x=read();x1=x2=0; if(!root||last==k) {last=k;add(root,x,0);continue;} before(root,x),after(root,x); if((!x2||x-t1<=t2-x)&&x1) ans=(ans+x-t1)%mod,dele(x1); else if(x2&&(!x1||t2-x<x-t1)) ans=(ans+t2-x)%mod,dele(x2); }新聞熱點
疑難解答
