首页 > 代码库 > BZOJ 1503: [NOI2004]郁闷的出纳员
BZOJ 1503: [NOI2004]郁闷的出纳员
题目
1503: [NOI2004]郁闷的出纳员
Time Limit: 5 Sec Memory Limit: 64 MBDescription
OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？
Input
Output
输出文件的行数为F命令的条数加一。对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。输出文件的最后一行包含一个整数，为离开公司的员工的总数。
Sample Input
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
Sample Output
10
20
-1
2
20
-1
2
HINT
I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000
Source
Splay
题解
这道题目就是就是寻找整个的第k大，以及删除和插入操作，我们可以使用SBT。Orz虽然下面说了splay。。。。【好吧，SBT练练手QAQ
代码
1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 using namespace std; 4 5 int Delta=0; 6 7 const int Maxn=1000000; 8 struct SBT{ 9 int left; 10 int right; 11 int size; 12 int key; 13 }; 14 SBT tree[Maxn+10]; 15 int root,cnt; 16 17 inline void rotate_l(int &x){ 18 int y=tree[x].right; 19 tree[x].right=tree[y].left; 20 tree[y].left=x; 21 tree[y].size=tree[x].size; 22 tree[x].size=1+tree[tree[x].left].size+tree[tree[x].right].size; 23 x=y; 24 } 25 26 inline void rotate_r(int &x){ 27 int y=tree[x].left; 28 tree[x].left=tree[y].right; 29 tree[y].right=x; 30 tree[y].size=tree[x].size; 31 tree[x].size=tree[tree[x].left].size+1+tree[tree[x].right].size; 32 x=y; 33 } 34 35 void maintain(int &x,bool flag){ 36 //printf("MainTain %d\n",x); 37 if (flag==false){ 38 if (tree[tree[tree[x].left].left].size>tree[tree[x].right].size){ 39 rotate_r(x); 40 } 41 else if (tree[tree[tree[x].left].right].size>tree[tree[x].right].size){ 42 rotate_l(tree[x].left); 43 rotate_r(x); 44 }else return ; 45 }else{ 46 if (tree[tree[tree[x].right].right].size>tree[tree[x].left].size){ 47 rotate_l(x); 48 }else if (tree[tree[tree[x].right].left].size>tree[tree[x].left].size){ 49 rotate_r(tree[x].right); 50 rotate_l(x); 51 }else return ; 52 } 53 maintain(tree[x].left,false); 54 maintain(tree[x].right,true); 55 maintain(x,true); 56 maintain(x,false); 57 } 58 void insert(int &x,int sp){ 59 if (!x){ 60 x=++cnt; 61 tree[x].left=tree[x].right=0; 62 tree[x].size=1; 63 tree[x].key=sp; 64 }else{ 65 tree[x].size++; 66 if (sp<tree[x].key){ 67 insert(tree[x].left,sp); 68 }else{ 69 insert(tree[x].right,sp); 70 } 71 maintain(x,sp>=tree[x].key); 72 } 73 } 74 75 /* 76 int del(int &x,int sp){ 77 tree[x].size--; 78 if (sp==tree[x].key || ( sp<tree[x].key && tree[x].left==0) || (sp>tree[x].key && tree[x].right==0)){ 79 int y=tree[x].key; 80 if (tree[x].left==0 ||tree[x].right==0){ 81 x=tree[x].left+tree[x].right; 82 }else{ 83 tree[x].key=del(tree[x].left,tree[x].key+1); 84 } 85 return y; 86 }else{ 87 if (sp<tree[x].key){ 88 return del(tree[x].left,sp); 89 }else{ 90 return del(tree[x].right,sp); 91 } 92 } 93 }*/ 94 95 void del(int &x,int mink){ 96 if (x==0) return; 97 if (tree[x].key+Delta<mink) 98 x=tree[x].right,del(x,mink); 99 else100 del(tree[x].left,mink),tree[x].size=tree[tree[x].left].size+1+tree[tree[x].right].size;101 }102 103 inline int getMax(){104 int i;105 for (i=root;tree[i].right;i=tree[i].right);106 return tree[i].key;107 }108 109 inline int getMin(){110 int i;111 for (i=root;tree[i].left;i=tree[i].left);112 return tree[i].key;113 }114 115 int rank(int &x,int sp){116 if (sp<tree[x].key){117 return rank(tree[x].left,sp);118 }else if (sp>tree[x].key){119 return rank(tree[x].right,sp)+tree[tree[x].left].size+1;120 }121 return tree[tree[x].left].size+1;122 }123 124 int select(int &x,int rak){125 int rk=tree[tree[x].left].size+1;126 if (rak<rk){127 return select(tree[x].left,rak);128 }else if (rak>rk){129 return select(tree[x].right,rak-rk);130 }131 return tree[x].key;132 }133 134 int pred(int &x,int y,int sp){135 if (x==0) return y;136 if (tree[x].key<sp){137 return pred(tree[x].right,x,sp);138 }139 return pred(tree[x].left,y,sp);140 }141 142 int succ(int &x,int y,int sp){143 if (x==0) return y;144 if (tree[x].key>sp){145 return succ(tree[x].left,x,sp);146 }147 return succ(tree[x].right,y,sp);148 }149 150 inline void init(){151 root=cnt=0;152 }153 154 int main(){155 init();156 int n,mink;157 scanf("%d%d",&n,&mink);158 for (int i=1;i<=n;i++){159 char c[10];int num;160 scanf("%s%d",&c,&num);161 if (c[0]==‘A‘) Delta+=num;162 if (c[0]==‘S‘) {163 Delta-=num;164 del(root,mink);165 }166 if (c[0]==‘I‘) {167 if (num<mink) continue;168 insert(root,num-Delta);169 }170 if (c[0]==‘F‘){171 if (num>tree[root].size){172 printf("-1\n");173 continue;174 }175 int Ans=select(root,tree[root].size-num+1);176 printf("%d\n",Ans+Delta);177 }178 }179 printf("%d\n",cnt-tree[root].size);180 return 0;181 }
BZOJ 1503: [NOI2004]郁闷的出纳员
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。