M_sea

洛谷1486 [NOI2004]郁闷的出纳员
题目描述OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工...
扫描右侧二维码阅读全文
26
2018/09

洛谷1486 [NOI2004]郁闷的出纳员

题目描述

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

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

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

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

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

传送门

算法

这个题有一个对于全体的修改。

考虑[NOIP2016]蚯蚓那个做法,维护一个变量add即可。

那么本题还需要以下操作:

  • 插入。考虑到add,需要把k减去add后再插入。
  • 删除小于k的所有节点。这个直接按k-1的权值分裂即可。同样要考虑add,所以实际上删除的是小于min-add的节点。而且删除时还要统计删除的节点个数。

然后就可以掉这个题。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100010;
int ans=0;

struct fhq_treap {
    int ch[MAXN][2];
    int sz[MAXN],val[MAXN],rnd[MAXN];
    int root,cnt;
    
    fhq_treap() { root=cnt=0; }
    inline void init() { root=cnt=0; }
    inline void pushup(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; }
    inline int new_node(int x) { sz[++cnt]=1,val[cnt]=x,rnd[cnt]=rand(); return cnt; }
    inline void split(int now,int k,int& x,int& y) {
        if (!now) { x=y=0; return; }
        if (val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
        else y=now,split(ch[now][0],k,x,ch[now][0]);
        pushup(now);
    }
    inline int merge(int A,int B) {
        if (!A||!B) return A+B;
        if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); pushup(A); return A; }
        else { ch[B][0]=merge(A,ch[B][0]); pushup(B); return B; }
    }
    inline int kth(int k) {
        int now=root;
        while (1) {
            if (k<=sz[ch[now][1]]) now=ch[now][1];
            else if (k==sz[ch[now][1]]+1) return now;
            else k-=sz[ch[now][1]]+1,now=ch[now][0];
        }
    }
    
    inline void insert(int k) {
        int x,y; split(root,k,x,y);
        root=merge(merge(x,new_node(k)),y);
    }
    inline void del(int k) { //删除小于k的数 
        int x,y; split(root,k-1,x,y);
        ans+=sz[x]; root=y;
    }
    inline void query(int k,int add) {
        if (k>sz[root]) puts("-1");
        else printf("%d\n",val[kth(k)]+add);
    }
};

fhq_treap T;

int main() {
    int add=0;
    int n=read(),Min=read();
    while (n--) {
        char op=getchar();
        while (!isalpha(op)) op=getchar();
        int k=read();
        if (op=='I'&&k>=Min) T.insert(k-add);
        else if (op=='A') add+=k;
        else if (op=='S') { add-=k; T.del(Min-add); } 
        else if (op=='F') T.query(k,add);
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 27 PM

发表评论

1 条评论

  1. smy

    菜鸡表示一个地方写错调了好久qwq