bzoj1503 郁闷的出纳员

bzoj1503 郁闷的出纳员

​​ 题目描述 OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。

老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。

好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内

输入输出格式 输入格式：

第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。

接下来的n行，每行表示一条命令。命令可以是以下四种之一：

名称 格式 作用

I命令 I_k 新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。

A命令 A_k 把每位员工的工资加上k

S命令 S_k 把每位员工的工资扣除k

F命令 F_k 查询第k多的工资

_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。

在初始时，可以认为公司里一个员工也没有。

输出格式：

输出文件的行数为F命令的条数加一。

对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。

输出文件的最后一行包含一个整数，为离开公司的员工的总数。

输入输出样例 输入样例#1： 复制

9 10 I 60 I 70 S 50 F 2 I 30 S 15 A 5 F 1 F 2 输出样例#1： 复制

10 20 -1 2 说明 I命令的条数不超过100000

A命令和S命令的总条数不超过100

F命令的条数不超过100000

每次工资调整的调整量不超过1000

新员工的工资不超过100000

注意这个工资的增加量 选择再开一个变量来储存 并且不能是 这个变量小于0了我才去减 而应该 只要我平衡树中有小于我工资要求的我就得删除 另外我之前的插入操作写的不是很好 但是zhx的就能过 而且常数很小%%%太强啦 我该如何才能像他一样强

#include#include#define inf 0x3f3f3f3f#define N 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; }inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x; }int root,size[N],value[N],child[N][2],cnt,fa[N],num[N],n,min1;inline void update(int x){ int l=child[x][0],r=child[x][1]; size[x]=size[l]+size[r]+num[x];}inline void rotate(int x,int &tar){ int y=fa[x],z=fa[y],l=child[y][1]==x,r=l^1; if (y==tar) tar=x;else child[z][child[z][1]==y]=x; fa[child[x][r]]=y;fa[y]=x;fa[x]=z; child[y][l]=child[x][r];child[x][r]=y;update(y);update(x);}inline void splay(int x,int &tar){ while(x!=tar){ int y=fa[x],z=fa[y]; if (y!=tar) if (child[y][0]==x^child[z][0]==y) rotate(x,tar);else rotate(y,tar); rotate(x,tar); }}void print(int x){ if (child[x][0]) print(child[x][0]); printf("value size father x childleft childright\n"); printf("%d %d %d %d %d %d\n",value[x],size[x],fa[x],x,child[x][0],child[x][1]); if (child[x][1]) print(child[x][1]);}inline void insert1(int &p,int x,int f){ if(!p){p=++cnt;value[p]=x;child[p][0]=child[p][1]=0;fa[p]=f;size[p]=num[p]=1;splay(p,root);return;} if(value[p]==x){num[p]++;size[p]++;splay(p,root);return;} if(xvalue[x]) if (child[x][1]) insert1(child[x][1],v);else value[++cnt]=v,child[x][1]=cnt,fa[cnt]=x,size[cnt]=1,num[cnt]=1,splay(cnt,root);update(x);}*/inline int find(int x,int pos){ int l=child[x][0]; if (pos>size[l]&&pos<=size[l]+num[x]) {splay(x,root);return value[x];} if (pos<=size[l]) return find(l,pos);else return find(child[x][1],pos-(size[l]+num[x])); }int ans;inline void succ(int x,int v){ if (!x) return;if (value[x]>=v){ans=x;succ(child[x][0],v);} else succ(child[x][1],v);}int leave=0;inline void delete1(int v){ ans=0;succ(root,v);if (!ans) {leave+=size[root];root=0;return;} splay(ans,root);leave+=size[child[ans][0]];fa[child[ans][0]]=0;child[ans][0]=0;update(ans);}int main(){// freopen("bzoj1503.in","r",stdin); n=read();min1=read();int add=0; for (int i=1;i<=n;++i){ char ch=gc(); while(ch!='A'&&ch!='I'&&ch!='S'&&ch!='F') ch=gc(); if (ch=='I'){int x=read();if (xsize[root]) printf("-1\n");else printf("%d\n",find(root,size[root]-x+1)+add);} //print(root);printf("adsfsad\n"); }printf("%d\n",leave); return 0;}

以前写过的treap版本的 还是split&merge的 还是指针的 比较naive的

#include #include #includestruct node{ node *left,*right; int s1,size,key,fix; node (int x){ left=right=NULL; size=1;s1=1;key=x;fix=rand(); }};node *root;int wage,min,n,ans,nn;bool flag;void updata(node *tree){ tree->size=tree->s1; if (tree->left!=NULL) tree->size+=tree->left->size; if (tree->right!=NULL) tree->size+=tree->right->size;}node* merge(node *tree1,node *tree2){ if (tree1==NULL) return tree2; if (tree2==NULL) return tree1; if (tree1->fixfix){ //merge 要比较 随机数 tree1->right=merge(tree1->right,tree2); updata(tree1); return tree1; }else{ tree2->left=merge(tree1,tree2->left); updata(tree2); return tree2; }}void splitup_key(node *root,node *&tree1,node *&tree2,int x){ if (root==NULL) { tree1=NULL;tree2=NULL; return; } if (root->keyright,tree1->right,tree2,x); updata(tree1); }else{ tree2=root; splitup_key(tree2->left,tree1,tree2->left,x); updata(tree2); }}void splitup_size(node *root,node *&tree1,node *&tree2,int x){ //1传递根指针2传递左右指针3传递需要删除的值 if (root==NULL){ tree1=NULL;tree2=NULL; return; } int tmp=(root->left!=NULL) ?root->left->size:0; if (x<=tmp){ tree2=root; splitup_size(tree2->left,tree1,tree2->left,x); updata(tree2); }else{ tree1=root; splitup_size(tree1->right,tree1->right,tree2,x-tmp-root->s1); updata(tree1); }}void delete1(int x){ //注意删除的时候 splitup_key只可将树拆分成比x小的放一堆 int aa=min-x; //此前写的 aa=min-x-1; node *p1,*p2; splitup_key(root,p1,p2,aa); //while(p1!=NULL) splitup_key(root,p1,p2,tmp); root=p2; if (p1!=NULL) ans+=p1->size;}int max1(node *tree){ if (tree==NULL) return -1; if (tree==NULL) return 00; int tmp=max1(tree->right); return (tmp==-1)?tree->key:tmp;}/*int check1(node *&tree,int x){ node *p1,*p2; splitup_size(tree,p1,p2,nn-ans-x+1); int tmp=max1(p1); tree=merge(p1,p2); return tmp;}*/int check2(node *tree,int x){// if (tree==NULL) { flag=false;return -1; } int tmpp=0; if (tree->left!=NULL) tmpp+=tree->left->size; // if (tmpps1) return tree->key; if (tmpp+tree->s1right,x-tmpp-tree->s1); } return check2(tree->left,x); }void print(node *tree){ if (tree==NULL) return; if (tree->left!=NULL) { print(tree->left); //printf("leftfinished\n"); } printf("%d %d %d %d\n",tree->key,tree->s1,tree->fix,tree->size);// if (tree->left!=NULL) printf("1\n"); if (tree->right!=NULL) { print(tree->right); // printf("rightfinished\n"); }}bool check(node *tree,int x){ if (tree==NULL) return false; //tree->size++; if (tree->key==x){ tree->s1+=1;tree->size++; return true; } if (tree->keyright,x); updata(tree); return tmp; }else{ bool tmp=check(tree->left,x); updata(tree); return tmp; }}int main(){ freopen("p1486.in","r",stdin); freopen("p1486.out","w",stdout); scanf("%d%d",&n,&min); wage=0; root=NULL; srand(time(0)); nn=0; for (int i=1;i<=n;++i){ int x; //scanf("%c",&o); char o[2]; scanf("%s%d",o,&x); //scanf("%d",&x); if (o[0]=='I'){ if (x>=min){ x-=wage;// 先判断是否大于min再 进行操作 if (check(root,x)==false){ // 有可能树中元素为-1 故修改原check node *p=new node(x); node *p1,*p2; splitup_key(root,p1,p2,x);//必须先拆分再根据随机数合并才可同时满足treap与二叉堆 root=merge(merge(p1,p),p2); } } //if (x>=min) root=merge(root,p),nn++; // print(root); // printf("asdfasdf %d,wage); continue; } if (o[0]=='A'){ wage+=x; continue; } if (o[0]=='S'){ wage-=x; delete1(wage);// 删除的时候 因为有可能树中元素为负数 所以修改了原来的删除方法 // print(root); // printf("deleted %d,wage); continue; } if (o[0]=='F'){ //如果k大于目前员工的数目，则输出-1. int size=0; flag=true; if (root) size=root->size; int tmp=check2(root,size-x+1); //print(root); //printf("asdklfj;l %d\n",wage); //printf("%d %d,size,size-x+1); if (flag==false) printf("-1\n");else printf("%d\n",tmp+wage); } } printf("%d\n",ans); //print(root); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。