自己的网站在哪做的忘了,环保业网站建设的策划,深圳做网站哪家公司最好,复旦学霸张立勇做的有关寺庙网站题目描述 凡凡开了一间宠物收养场。收养场提供两种服务#xff1a;收养被主人遗弃的宠物和让新的主人领养这些宠物。 每个领养者都希望领养到自己满意的宠物#xff0c;凡凡根据领养者的要求通过他自己发明的一个特殊的公式#xff0c;得出该领养者希望领养的宠物的特点值a收养被主人遗弃的宠物和让新的主人领养这些宠物。 每个领养者都希望领养到自己满意的宠物凡凡根据领养者的要求通过他自己发明的一个特殊的公式得出该领养者希望领养的宠物的特点值aa是一个正整数a2^31而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了宠物收养场总是会有两种情况发生被遗弃的宠物过多或者是想要收养宠物的人太多而宠物太少。 被遗弃的宠物过多时假若到来一个领养者这个领养者希望领养的宠物的特点值为a那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。任何两只宠物的特点值都不可能是相同的任何两个领养者的希望领养宠物的特点值也不可能是一样的如果有两只满足要求的宠物即存在两只宠物他们的特点值分别为a-b和ab那么领养者将会领养特点值为a-b的那只宠物。 收养宠物的人过多假若到来一只被收养的宠物那么哪个领养者能够领养它呢能够领养它的领养者是那个希望被领养宠物的特点值最接近该宠物特点值的领养者如果该宠物的特点值为a存在两个领养者他们希望领养宠物的特点值分别为a-b和ab那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物而它本身希望领养的宠物的特点值为b那么这个领养者的不满意程度为abs(a-b)。 你得到了一年当中领养者和被收养宠物到来收养所的情况请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时收养所里面既没有宠物也没有领养者。 输入输出格式 输入格式 第一行为一个正整数nn80000表示一年当中来到收养场的宠物和领养者的总数。接下来的n行按到来时间的先后顺序描述了一年当中来到收养场的宠物和领养者的情况。每行有两个正整数a, b其中a0表示宠物a1表示领养者b表示宠物的特点值或是领养者希望领养宠物的特点值。同一时间呆在收养所中的要么全是宠物要么全是领养者这些宠物和领养者的个数不会超过10000个 输出格式 仅有一个正整数表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。 输入输出样例 输入样例#1 复制 5
0 2
0 4
1 3
1 2
1 5输出样例#1 复制 3
注abs(3-2) abs(2-4)3
最后一个领养者没有宠物可以领养。哎呀一不小心拿了个rank1还比第二快9倍呢:joy: 这道题目比较简单 请选择一种数据结构 支持插入、删除、求前驱后继 splay裸题 有一个小技巧 在求前驱后继的时候增加两个哨兵节点 这样就不会加爆了 #includeiostream
#includecstdio
#includecstdlib
using namespace std;
const int MAXN1e610;
const int mod1000000;
const int INF2*0x7ffffff;
inline char nc()
{static char buf[MAXN],*p1buf,*p2buf;return p1p2(p2(p1buf)fread(buf,1,MAXN,stdin))?EOF:*p1;
}
inline int read()
{char cnc();int x0,f1;while(c0||c9){if(c-)f-1;cnc();}while(c0c9){xx*10c-0,cnc();}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].fafa;tree[fa].ch[how]x;
}
void rotate(int x)
{int Ytree[x].fa;int Rtree[Y].fa;int Ysonident(x);int Rsonident(Y);int Btree[x].ch[Yson^1];connect(B,Y,Yson);connect(Y,x,Yson^1);connect(x,R,Rson);
}
void splay(int x,int to)
{totree[to].fa;while(tree[x].fa!to){if(tree[tree[x].fa].fato) 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].vx;tree[tot].fafa;tree[tot].rec1;
}
void insert(int x)
{point;if(tot0){newpoint(x,0);roottot;return ;}int nowroot;while(1){if(tree[now].vx){tree[now].rec;splay(now,root);return ;}int nxtxtree[now].v?0:1;if(!tree[now].ch[nxt]){newpoint(x,now);tree[now].ch[nxt]tot;splay(tot,root);return ;}nowtree[now].ch[nxt];}
}
int lower(int x)
{int ans-INF;int nowroot;while(now){if(tree[now].vx) ansmax(ans,tree[now].v);int nxtxtree[now].v?0:1;if(tree[now].ch[nxt]0) return ans;nowtree[now].ch[nxt];}return ans;
}
int upper(int x)
{int ansINF;int nowroot;while(now){if(tree[now].vx) ansmin(ans,tree[now].v);int nxtxtree[now].v?0:1;if(tree[now].ch[nxt]0) return ans;nowtree[now].ch[nxt];}
}
int find(int x)
{int nowroot;while(1){if(tree[now].vx) {splay(now,root);return now;}int nxtxtree[now].v?0:1;if(!tree[now].ch[nxt]) return 0;nowtree[now].ch[nxt];}
}
void des(int x)
{tree[x].ch[0]tree[x].ch[1]tree[x].fatree[x].rectree[x].v0;if(xtot) tot--;
}
void dele(int x)
{int dealfind(x);if(!deal) return ;point--;if(tree[deal].rec1){tree[deal].rec--;return ;}if(!tree[deal].ch[0]) roottree[deal].ch[1],tree[root].fa0;else{int mxsontree[deal].ch[0];while(tree[mxson].ch[1]) mxsontree[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 nread(),ans0;while(n--){int optread(),xread();if(PetNum0) {insert(x);if(opt0) PetNum;else PetNum--;}else if(PetNum0){if(opt0) insert(x),PetNum;else {int prelower(x);int latupper(x);if(abs(pre-x)abs(x-lat)) dele(pre),ans(ansabs(pre-x))%mod;else dele(lat),ans(ansabs(lat-x))%mod;PetNum--;}}else{if(opt1) insert(x),PetNum--;else{int prelower(x);int latupper(x);if((abs(pre-x))abs(x-lat)) dele(pre),ans(ansabs(pre-x))%mod;//这里写小于等于和小于一样 else dele(lat),ans(ansabs(lat-x))%mod;PetNum;}}}printf(%d,ans);
} 转载于:https://www.cnblogs.com/zwfymqz/p/7895794.html
