c/c++语言开发共享[luogu1486][郁闷的出纳员]

题目链接

思路

这个题其实就是对于treap中的删除操作进行一些修改。自己yy了一种做法。就是在删除的时候，如果要删除的数比这棵子树的根大，那么就把根变成根的右孩子，这样就相当于删除了整棵左子树和根节点。然后重新维护一下siz，并且维护一下平衡性就行了。

竟然把rotate函数写错了。调了30min。又没正确理解

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

这句话的含义，又调了30min。23333

代码

//每次修改操作之后都进行一次删除，并且更改删除函数 /* * @author: wxyww * @date:   2018-12-02 08:41:38 * @last modified time: 2018-12-02 10:02:49 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> using namespace std; #define ls tr[cur].ch[0] #define rs tr[cur].ch[1] typedef long long ll; const int n = 100000 + 100,inf = 1e9 + 7; ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } struct node {     int ch[2],id,val,siz,cnt; }tr[n]; int min; void up(int cur) {     tr[cur].siz = tr[ls].siz + tr[rs].siz + tr[cur].cnt; } void rotate(int &cur,int f) {     int son = tr[cur].ch[f];     tr[cur].ch[f] = tr[son].ch[f ^ 1];     tr[son].ch[f ^ 1] = cur;     up(cur);     cur = son;     up(cur); } int tot; void insert(int &cur,int val) {     if(!cur) {         cur = ++tot;         tr[cur].id = rand();         tr[cur].val = val;         tr[cur].siz = tr[cur].cnt = 1;         return;     }     tr[cur].siz++;     if(val == tr[cur].val) {tr[cur].cnt++;return;}     int d = val > tr[cur].val;     insert(tr[cur].ch[d],val);     if(tr[tr[cur].ch[d]].id < tr[cur].id) rotate(cur,d); } void del(int &cur,int val) {     if(!cur) return;     if(val <= tr[cur].val) del(ls,val);     else {         del(rs,val);         cur = rs;     }     up(cur);     if(tr[ls].id < tr[cur].id && ls) rotate(cur,0);     if(tr[rs].id < tr[cur].id && rs) rotate(cur,1); } int kth(int cur,int now) {     while(1) {         if(now > tr[rs].siz + tr[cur].cnt) now -= tr[rs].siz + tr[cur].cnt,cur = ls;         else if(now <= tr[rs].siz) cur = rs;         else return tr[cur].val;      } } int main() {     int rt = 0;     int n = read(),change = 0,num = 0;     min = read();     char c;     while(n--) {         int x;         scanf("n%c %d",&c,&x);         if(c == 'i') {             x -= change;             if(x >= min) num++,insert(rt,x);         }         if(c == 'a') min -= x,change += x;         if(c == 's') {             min += x;             del(rt,min);             change -= x;         }         if(c == 'f') {             if(x > tr[rt].siz) puts("-1");             else printf("%dn",kth(rt,x) + change);         }     }     cout<<num - tr[rt].siz<<endl;     return 0; }

一言

时间会把你欠下的对不起，变成还不起，又会把很多对不起，变成来不及。 ——乖，摸摸头