bzoj1503 郁闷的出纳员

http://www.elijahqi.win/archives/1763

题目描述

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：复制

-1

说明

I命令的条数不超过100000

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

F命令的条数不超过100000

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

新员工的工资不超过100000

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

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

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

#include <cstdio>
#include<ctime> 
#include<cstdlib>
struct node
{
    node *left,*right;
    int s1,size,key,fix;
    node (int x){
        left=right=NULL;
        size=;s1=;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->fix<tree2->fix){  //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->key<x){
        tree1=root;
        splitup_key(tree1->right,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){   //传递根指针传递左右指针传递需要删除的值
    if (root==NULL){
        tree1=NULL;tree2=NULL;
        return;
    }
    int tmp=(root->left!=NULL) ?root->left->size:;
    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-;
    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 -;
    if (tree==NULL) return ;
    int tmp=max1(tree->right);
    return (tmp==-)?tree->key:tmp;
}
/*int check1(node *&tree,int x){
    node *p1,*p2;
    splitup_size(tree,p1,p2,nn-ans-x+);
    int tmp=max1(p1);
    tree=merge(p1,p2);
    return tmp;
}*/
int check2(node *tree,int x){//
    if (tree==NULL) {
        flag=false;return -;
    }
    int tmpp=;
    if (tree->left!=NULL) tmpp+=tree->left->size; 
    //
    if (tmpp<x&&x<=tmpp+tree->s1) return tree->key; 
    if (tmpp+tree->s1<x) {
        return check2(tree->right,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+=;tree->size++;
        return true;
    }
    if (tree->key<x){
        bool tmp=check(tree->right,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=;
    root=NULL;
    srand(time());
    nn=;
    for (int i=;i<=n;++i){
        int x;
        //scanf("%c",&o);
        char o[];
        scanf("%s%d",o,&x);
        //scanf("%d",&x);
        if (o[]=='I'){

            if (x>=min){
                x-=wage;// 先判断是否大于min再 进行操作
                if (check(root,x)==false){   // 有可能树中元素为- 故修改原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 \n",wage);
            continue;
        }
        if (o[]=='A'){
            wage+=x;
            continue;
        }
        if (o[]=='S'){
            wage-=x;
            delete1(wage);//  删除的时候 因为有可能树中元素为负数 所以修改了原来的删除方法
        //    print(root);
        //    printf("deleted %d \n",wage);
            continue;
        }
        if (o[]=='F'){
            //如果k大于目前员工的数目，则输出-.
            int size=;
            flag=true;
            if (root) size=root->size;
            int tmp=check2(root,size-x+);
            //print(root);
            //printf("asdklfj;l %d\n",wage);
            //printf("%d %d ",size,size-x+);
            if (flag==false) printf("-1\n");else
            printf("%d\n",tmp+wage);
        }

    }
    printf("%d\n",ans);
    //print(root);
    return ;
}

bzoj1503 郁闷的出纳员

继续阅读

codeforces 38G Queue

UVa 11922 - Permutation Transformer （Splay） Permutation Transformer

[BZOJ2733] [HNOI2012]永无乡 && splay

BZOJ 2733 [HNOI2012]永无乡 Treap + 并查集题目链接题意思路Code

P3391 文艺平衡树（Splay区间翻转）

伸展树(splay)

POJ3580 SuperMemo SPLAY 各种操作。。。。

Splay 区间反转

splay的入门

SPLAY① 入门引入splay的构建注意事项splay应用

[CodeVS 1343] 蚱蜢：Splay Tree

POJ 3580 SuperMemo splay 翻转右移

luogu4715 「英语」Z 语言

tyvj P1185 营业额统计

戴尔推出了新款49英寸带鱼屏显示器U4924DW，首发价为10699元。它采用了IPSBlack面板，拥有5120×14

CSU 1811 Tree Intersection（Treap启发式合并）