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啟發式合并）