「BZOJ1208」[HNOI2004] 宠物收养所
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
0 2
0 4
1 3
1 2
1 5
Sample Output
(abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养)
题解
如果收养者按照到来顺序收养宠物的话，只要把宠物的特点值建立平衡树，每次求收养者特点值前驱后继与之绝对值相差较小的一个
这就是一个set的简单应用啦
对于100%的数据，人和宠物互相选择，可以用两个平衡树，实现起来有些麻烦
但我们可以想到，人和宠物在此题本质等价，人和宠物都可能待在店里等待
那其实只要一个平衡树，再加一个变量记录一下当前树中存的是人还是宠物即可，具体见代码
80% 用队列和set实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000 #define pi acos(-1) #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll 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-'0';ch=getchar();} return x*f; } int t,n,ans; set<int>st; queue<int>que; void query(int x) { set<int>::iterator l=--st.lower_bound(x),r=st.lower_bound(x); if(x-*l<=*r-x&&*l!=-inf) { ans+=x-*l; st.erase(l); } else { ans+=*r-x; st.erase(r); } ans%=mod; } int main() { st.insert(inf); st.insert(-inf); n=read(); for(int i=1;i<=n;i++) { int a=read(),b=read(); if(a==1)st.insert(b); else que.push(b); if(!que.empty()&&st.size()!=2) { int t=que.front(); que.pop(); query(t); } } printf("%d",ans); return 0; } |
100% set
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000 #define pi acos(-1) #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll 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-'0';ch=getchar();} return x*f; } int t,n,ans; set<int>st; void query(int x) { set<int>::iterator l=--st.lower_bound(x),r=st.lower_bound(x); if(x-*l<=*r-x&&*l!=-inf) { ans+=x-*l; st.erase(l); } else { ans+=*r-x; st.erase(r); } ans%=mod; } int main() { st.insert(inf); st.insert(-inf); n=read(); for(int i=1;i<=n;i++) { int a=read(),b=read(); if(st.size()==2) { t=a; st.insert(b); } else if(a==t)st.insert(b); else query(b); } printf("%d",ans); return 0; } |
splay模板练习
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include<iostream> #include<cstdio> using namespace std; int n,size,rt,kind,t1,t2; long long ans; int tr[80001][2],num[80001],fa[80001]; void rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; if(tr[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x; else{if(tr[z][0]==y)tr[z][0]=x;else tr[z][1]=x;} fa[x]=z;fa[y]=x;fa[tr[x][r]]=y; tr[y][l]=tr[x][r];tr[x][r]=y; } void splay(int x,int &k) { int y,z; while(x!=k) { y=fa[x],z=fa[y]; if(y!=k) { if((tr[y][0]==x)^(tr[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); } } void ins(int &k,int x,int last) { if(k==0){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;} if(x<num[k])ins(tr[k][0],x,k);else ins(tr[k][1],x,k); } void del(int x) { splay(x,rt); if(tr[x][0]*tr[x][1]==0) {rt=tr[x][0]+tr[x][1];} else { int k=tr[x][1]; while(tr[k][0])k=tr[k][0]; tr[k][0]=tr[x][0];fa[tr[x][0]]=k; rt=tr[x][1]; } fa[rt]=0; } void ask_before(int k,int x) { if(k==0)return; if(num[k]<=x){t1=k;ask_before(tr[k][1],x);} else ask_before(tr[k][0],x); } void ask_after(int k,int x) { if(k==0)return; if(num[k]>=x){t2=k;ask_after(tr[k][0],x);} else ask_after(tr[k][1],x); } int main() { scanf("%d",&n); int f,x; for(int i=1;i<=n;i++) { scanf("%d%d",&f,&x); if(!rt){kind=f;ins(rt,x,0);} else if(kind==f){ins(rt,x,0);} else { t1=t2=-1; ask_before(rt,x);ask_after(rt,x); if(t1==-1){ans+=num[t2]-x;ans%=1000000;del(t2);} else if(t2==-1){ans+=x-num[t1];ans%=1000000;del(t1);} else { if(x-num[t1]>num[t2]-x) {ans+=num[t2]-x;ans%=1000000;del(t2);} else{ans+=x-num[t1];ans%=1000000;del(t1);} } } } cout<<ans<<endl; return 0; } |
OI 课件=>
long long没有必要？
大神可认识林伟鸿？
学长不是写过这题了吗。。= =
最近在整理东西给学弟讲课
太强了，前排膜拜
然而set碰到重复的不会gg？
任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的
哦我没仔细看题。。%%%