1208: [HNOI2004]寵物收養(yǎng)所 Time Limit: 10 Sec Memory Limit: 162 MB Description 最近，阿Q開了一間寵物收養(yǎng)所。收養(yǎng)所提供兩種服務(wù)：收養(yǎng)被主人遺棄的寵物和讓新的主人領(lǐng)養(yǎng)這些寵物。每個(gè)領(lǐng)養(yǎng)者都希望領(lǐng)養(yǎng)到自己滿意的寵物，阿Q根據(jù)領(lǐng)養(yǎng)者的要求通過他自己發(fā)明的一個(gè)特殊的公式，得出該領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)的寵物的特點(diǎn)值a（a是一個(gè)正整數(shù)，a<2^31），而他也給每個(gè)處在收養(yǎng)所的寵物一個(gè)特點(diǎn)值。這樣他就能夠很方便的處理整個(gè)領(lǐng)養(yǎng)寵物的過程了，寵物收養(yǎng)所總是會(huì)有兩種情況發(fā)生：被遺棄的寵物過多或者是想要收養(yǎng)寵物的人太多，而寵物太少。 1． 被遺棄的寵物過多時(shí)，假若到來一個(gè)領(lǐng)養(yǎng)者，這個(gè)領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)的寵物的特點(diǎn)值為a，那么它將會(huì)領(lǐng)養(yǎng)一只目前未被領(lǐng)養(yǎng)的寵物中特點(diǎn)值最接近a的一只寵物。（任何兩只寵物的特點(diǎn)值都不可能是相同的，任何兩個(gè)領(lǐng)養(yǎng)者的希望領(lǐng)養(yǎng)寵物的特點(diǎn)值也不可能是一樣的）如果有兩只滿足要求的寵物，即存在兩只寵物他們的特點(diǎn)值分別為a-b和a+b，那么領(lǐng)養(yǎng)者將會(huì)領(lǐng)養(yǎng)特點(diǎn)值為a-b的那只寵物。 2． 收養(yǎng)寵物的人過多，假若到來一只被收養(yǎng)的寵物，那么哪個(gè)領(lǐng)養(yǎng)者能夠領(lǐng)養(yǎng)它呢？能夠領(lǐng)養(yǎng)它的領(lǐng)養(yǎng)者，是那個(gè)希望被領(lǐng)養(yǎng)寵物的特點(diǎn)值最接近該寵物特點(diǎn)值的領(lǐng)養(yǎng)者，如果該寵物的特點(diǎn)值為a，存在兩個(gè)領(lǐng)養(yǎng)者他們希望領(lǐng)養(yǎng)寵物的特點(diǎn)值分別為a-b和a+b，那么特點(diǎn)值為a-b的那個(gè)領(lǐng)養(yǎng)者將成功領(lǐng)養(yǎng)該寵物。 一個(gè)領(lǐng)養(yǎng)者領(lǐng)養(yǎng)了一個(gè)特點(diǎn)值為a的寵物，而它本身希望領(lǐng)養(yǎng)的寵物的特點(diǎn)值為b，那么這個(gè)領(lǐng)養(yǎng)者的不滿意程度為abs(a-b)。【任務(wù)描述】你得到了一年當(dāng)中，領(lǐng)養(yǎng)者和被收養(yǎng)寵物到來收養(yǎng)所的情況，希望你計(jì)算所有收養(yǎng)了寵物的領(lǐng)養(yǎng)者的不滿意程度的總和。這一年初始時(shí)，收養(yǎng)所里面既沒有寵物，也沒有領(lǐng)養(yǎng)者。 Input 第一行為一個(gè)正整數(shù)n，n<=80000，表示一年當(dāng)中來到收養(yǎng)所的寵物和領(lǐng)養(yǎng)者的總數(shù)。接下來的n行，按到來時(shí)間的先后順序描述了一年當(dāng)中來到收養(yǎng)所的寵物和領(lǐng)養(yǎng)者的情況。每行有兩個(gè)正整數(shù)a, b，其中a=0表示寵物，a=1表示領(lǐng)養(yǎng)者，b表示寵物的特點(diǎn)值或是領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)寵物的特點(diǎn)值。（同一時(shí)間呆在收養(yǎng)所中的，要么全是寵物，要么全是領(lǐng)養(yǎng)者，這些寵物和領(lǐng)養(yǎng)者的個(gè)數(shù)不會(huì)超過10000個(gè)） Output 僅有一個(gè)正整數(shù)，表示一年當(dāng)中所有收養(yǎng)了寵物的領(lǐng)養(yǎng)者的不滿意程度的總和mod 1000000以后的結(jié)果。 Sample Input 5 0 2 0 4 1 3 1 2 1 5 Sample Output 3 (abs(3-2) + abs(2-4)=3，最后一個(gè)領(lǐng)養(yǎng)者沒有寵物可以領(lǐng)養(yǎng))
/*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);//轉(zhuǎn)根. 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); }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
