1208: [HNOI2004]寵物收養(yǎng)所

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?9775??Solved:?3918
[Submit][Status][Discuss]

Description

最近，阿Q開(kāi)了一間寵物收養(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)者的要求通過(guò)他自己發(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)寵物的過(guò)程了，寵物收養(yǎng)所總是會(huì)有兩種情況發(fā)生：被遺棄的寵物過(guò)多或者是想要收養(yǎng)寵物的人太多，而寵物太少。 1． 被遺棄的寵物過(guò)多時(shí)，假若到來(lái)一個(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)寵物的人過(guò)多，假若到來(lái)一只被收養(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)寵物到來(lái)收養(yǎng)所的情況，希望你計(jì)算所有收養(yǎng)了寵物的領(lǐng)養(yǎng)者的不滿意程度的總和。這一年初始時(shí)，收養(yǎng)所里面既沒(méi)有寵物，也沒(méi)有領(lǐng)養(yǎng)者。

Input

第一行為一個(gè)正整數(shù)n，n<=80000，表示一年當(dāng)中來(lái)到收養(yǎng)所的寵物和領(lǐng)養(yǎng)者的總數(shù)。接下來(lái)的n行，按到來(lái)時(shí)間的先后順序描述了一年當(dāng)中來(lái)到收養(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ì)超過(guò)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)者沒(méi)有寵物可以領(lǐng)養(yǎng))

HINT

Source

依舊模板：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int MOD=1000000; const int MAXN=1000009; int Abs(int a) { return a>=0?a:-a; } int fa[MAXN],ch[MAXN][2],key[MAXN],cnt[MAXN],size[MAXN],root,sz; void init() {root=sz=0;memset(ch,0,sizeof(ch));memset(fa,0,sizeof(fa));memset(cnt,0,sizeof(cnt));memset(size,0,sizeof(size)); } inline void clear(int x) { fa[x]=ch[x][0]=ch[x][1]=cnt[x]=size[x]=0; } inline int get(int x) { return ch[fa[x]][1]==x; } inline void update(int x) {if(x){size[x]=cnt[x];if(ch[x][0]) size[x]+=size[ch[x][0]];if(ch[x][1]) size[x]+=size[ch[x][1]];} } inline void rotate(int x) {int father=fa[x],ffather=fa[father],which=get(x);ch[father][which]=ch[x][!which];fa[ch[father][which]]=father;ch[x][!which]=father;fa[father]=x;fa[x]=ffather;if(ffather) ch[ffather][ch[ffather][1]==father]=x;update(father);update(x); } inline void splay(int x) {for(int father;(father=fa[x]);rotate(x))if(fa[father])rotate((get(x)==get(father)?father:x));root=x; } inline void insert(int x) {if(root==0) { root=++sz;fa[sz]=ch[sz][0]=ch[sz][1]=0;cnt[sz]=size[sz]=1;key[sz]=x;return; }int now=root,father=0;while(1){if(key[now]==x) { cnt[now]++;update(now);update(father);splay(now);return; }father=now;now=ch[father][key[now]<x];if(now==0){sz++;fa[sz]=father;ch[father][key[father]<x]=sz;ch[sz][0]=ch[sz][1]=0;cnt[sz]=size[sz]=1;key[sz]=x;update(father);splay(sz);return;}} } inline int find(int x)//找到x的位置 {int now=root,ans=0;while(1){if(x<key[now]) now=ch[now][0];else{if(ch[now][0]) ans+=size[ch[now][0]];if(x==key[now]) { splay(now);return ans+1; }ans+=cnt[now];now=ch[now][1];}} } inline int rank(int x)//找到排名為x的數(shù) {int now=root;while(1){if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0];else{int tmp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];if(x<=tmp) return key[now];x=x-tmp;now=ch[now][1];}} } inline int pre()//找前驅(qū) {int now=ch[root][0];while(ch[now][1]) now=ch[now][1];return now; } inline int suf()//找后繼 {int now=ch[root][1];while(ch[now][0]) now=ch[now][0];return now; } inline void del(int x)//刪去一個(gè)x {find(x);if(cnt[root]>1) { cnt[root]--;update(root);return; }else if(!ch[root][0]&&!ch[root][1]) { root=sz=0;clear(root);return; }else if(!ch[root][0]){int oldroot=root;root=ch[root][1];fa[root]=0;clear(oldroot);return;}else if(!ch[root][1]){int oldroot=root;root=ch[root][0];fa[root]=0;clear(oldroot);return;}int leftbig=pre(),oldroot=root;splay(leftbig);ch[root][1]=ch[oldroot][1];fa[ch[root][1]]=root;clear(oldroot);update(root); } int main() {//freopen("in.txt","r",stdin);int n,a,b,flag=0,sum=0;ll ans=0;init();scanf("%d",&n);while(n--){scanf("%d%d",&a,&b);if(flag==a||sum==0){insert(b);flag=a;sum++;}else if(flag==(!a)&&sum){insert(b);if(cnt[root]>1) del(b);else{int tmp1=pre(),tmp2=suf();tmp1=(tmp1==0?-1:key[tmp1]);tmp2=(tmp2==0?-1:key[tmp2]);if(tmp1==-1) { ans+=Abs(b-tmp2);del(tmp2); }else if(tmp2==-1) { ans+=Abs(b-tmp1);del(tmp1); }else if(Abs(b-tmp1)<=Abs(b-tmp2)){ans+=Abs(b-tmp1);del(tmp1);}else{ans+=Abs(b-tmp2);del(tmp2);}ans%=MOD;}del(b);sum--;}}printf("%lld\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/--ZHIYUAN/p/7811565.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 1208的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。