題目描述

凡凡開了一間寵物收養(yǎng)場。收養(yǎng)場提供兩種服務：收養(yǎng)被主人遺棄的寵物和讓新的主人領養(yǎng)這些寵物。

每個領養(yǎng)者都希望領養(yǎng)到自己滿意的寵物，凡凡根據(jù)領養(yǎng)者的要求通過他自己發(fā)明的一個特殊的公式，得出該領養(yǎng)者希望領養(yǎng)的寵物的特點值a（a是一個正整數(shù)，a<2^31），而他也給每個處在收養(yǎng)場的寵物一個特點值。這樣他就能夠很方便的處理整個領養(yǎng)寵物的過程了，寵物收養(yǎng)場總是會有兩種情況發(fā)生：被遺棄的寵物過多或者是想要收養(yǎng)寵物的人太多，而寵物太少。

被遺棄的寵物過多時，假若到來一個領養(yǎng)者，這個領養(yǎng)者希望領養(yǎng)的寵物的特點值為a，那么它將會領養(yǎng)一只目前未被領養(yǎng)的寵物中特點值最接近a的一只寵物。（任何兩只寵物的特點值都不可能是相同的，任何兩個領養(yǎng)者的希望領養(yǎng)寵物的特點值也不可能是一樣的）如果有兩只滿足要求的寵物，即存在兩只寵物他們的特點值分別為a-b和a+b，那么領養(yǎng)者將會領養(yǎng)特點值為a-b的那只寵物。

收養(yǎng)寵物的人過多，假若到來一只被收養(yǎng)的寵物，那么哪個領養(yǎng)者能夠領養(yǎng)它呢？能夠領養(yǎng)它的領養(yǎng)者，是那個希望被領養(yǎng)寵物的特點值最接近該寵物特點值的領養(yǎng)者，如果該寵物的特點值為a，存在兩個領養(yǎng)者他們希望領養(yǎng)寵物的特點值分別為a-b和a+b，那么特點值為a-b的那個領養(yǎng)者將成功領養(yǎng)該寵物。

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

你得到了一年當中，領養(yǎng)者和被收養(yǎng)寵物到來收養(yǎng)所的情況，請你計算所有收養(yǎng)了寵物的領養(yǎng)者的不滿意程度的總和。這一年初始時，收養(yǎng)所里面既沒有寵物，也沒有領養(yǎng)者。

輸入輸出格式

輸入格式：

?

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

?

輸出格式：

?

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

?

輸入輸出樣例

輸入樣例#1：?復制 5 0 2 0 4 1 3 1 2 1 5 輸出樣例#1：?復制 3 注：abs(3-2) + abs(2-4)=3， 最后一個領養(yǎng)者沒有寵物可以領養(yǎng)。

?

?

哎呀一不小心拿了個rank1還比第二快9倍呢:joy:

這道題目比較簡單

請選擇一種數(shù)據(jù)結構，

支持插入、刪除、求前驅后繼

splay裸題

有一個小技巧：

在求前驅后繼的時候增加兩個哨兵節(jié)點

這樣就不會加爆了

?

#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; const int MAXN=1e6+10; const int mod=1000000; const int INF=2*0x7ffffff; inline char nc() {static char buf[MAXN],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin))?EOF:*p1++; } inline int read() {char c=nc();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}return x*f; } int PetNum; #define root tree[0].ch[1] struct node {int v,fa,ch[2],rec; }tree[MAXN];int tot,point; bool ident(int x) {return tree[tree[x].fa].ch[0]==x?0:1; } void connect(int x,int fa,int how) {tree[x].fa=fa;tree[fa].ch[how]=x; } void rotate(int x) {int Y=tree[x].fa;int R=tree[Y].fa;int Yson=ident(x);int Rson=ident(Y);int B=tree[x].ch[Yson^1];connect(B,Y,Yson);connect(Y,x,Yson^1);connect(x,R,Rson); } void splay(int x,int to) {to=tree[to].fa;while(tree[x].fa!=to){if(tree[tree[x].fa].fa==to) rotate(x);else if(ident(x)==ident(tree[x].fa)) rotate(tree[x].fa),rotate(x);else rotate(x),rotate(x);} } void newpoint(int x,int fa) {tree[++tot].v=x;tree[tot].fa=fa;tree[tot].rec=1; } void insert(int x) {point++;if(tot==0){newpoint(x,0);root=tot;return ;}int now=root;while(1){if(tree[now].v==x){tree[now].rec++;splay(now,root);return ;}int nxt=x<tree[now].v?0:1;if(!tree[now].ch[nxt]){newpoint(x,now);tree[now].ch[nxt]=tot;splay(tot,root);return ;}now=tree[now].ch[nxt];} } int lower(int x) {int ans=-INF;int now=root;while(now){if(tree[now].v<x) ans=max(ans,tree[now].v);int nxt=x<tree[now].v?0:1;if(tree[now].ch[nxt]==0) return ans;now=tree[now].ch[nxt];}return ans; } int upper(int x) {int ans=INF;int now=root;while(now){if(tree[now].v>x) ans=min(ans,tree[now].v);int nxt=x<tree[now].v?0:1;if(tree[now].ch[nxt]==0) return ans;now=tree[now].ch[nxt];} } int find(int x) {int now=root;while(1){if(tree[now].v==x) {splay(now,root);return now;}int nxt=x<tree[now].v?0:1;if(!tree[now].ch[nxt]) return 0;now=tree[now].ch[nxt];} } void des(int x) {tree[x].ch[0]=tree[x].ch[1]=tree[x].fa=tree[x].rec=tree[x].v=0;if(x==tot) tot--; } void dele(int x) {int deal=find(x);if(!deal) return ;point--;if(tree[deal].rec>1){tree[deal].rec--;return ;}if(!tree[deal].ch[0]) root=tree[deal].ch[1],tree[root].fa=0;else{int mxson=tree[deal].ch[0];while(tree[mxson].ch[1]) mxson=tree[mxson].ch[1];splay(mxson,tree[deal].ch[0]);connect(tree[deal].ch[1],mxson,1);connect(mxson,0,1);}des(deal); } int main() {#ifdef WIN32freopen("a.in","r",stdin);#else#endifint n=read(),ans=0;while(n--){int opt=read(),x=read();if(PetNum==0) {insert(x);if(opt==0) PetNum++;else PetNum--;}else if(PetNum>0){if(opt==0) insert(x),PetNum++;else {int pre=lower(x);int lat=upper(x);if(abs(pre-x)<=abs(x-lat)) dele(pre),ans=(ans+abs(pre-x))%mod;else dele(lat),ans=(ans+abs(lat-x))%mod;PetNum--;}}else{if(opt==1) insert(x),PetNum--;else{int pre=lower(x);int lat=upper(x);if((abs(pre-x))<abs(x-lat)) dele(pre),ans=(ans+abs(pre-x))%mod;//這里寫小于等于和小于一樣 else dele(lat),ans=(ans+abs(lat-x))%mod;PetNum++;}}}printf("%d",ans); }

?

?

?

?

轉載于:https://www.cnblogs.com/zwfymqz/p/7895794.html

總結

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

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