[luogu1486][郁闷的出纳员]
程序员文章站
2022-03-26 13:57:45
思路
这个题其实就是对于treap中的删除操作进行一些修改。自己yy了一种做法。就是在删除的时候,如果要删除的数比这棵子树的根大,那么就把根变成根的右孩子,这样就相当于删除了整棵左子树和根节点。然后重新维护一 ......
题目链接
思路
这个题其实就是对于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("%d\n",kth(rt,x) + change); } } cout<<num - tr[rt].siz<<endl; return 0; }
一言
时间会把你欠下的对不起,变成还不起,又会把很多对不起,变成来不及。 ——乖,摸摸头
上一篇: 在Android平台使用SNPE应链接libc++库
下一篇: 算法第三章实践报告