1503: [NOI2004]郁悶的出納員
時間限制: 5 Sec 記憶體限制: 64 MB
送出: 1530 解決: 538
[ 送出][ ][ ]
題目描述
OIER公司是一家大型專業化軟體公司,有着數以萬計的員工。作為一名出納員,我的任務之一便是統計每位員工的工資。這本來是一份不錯的工作,但是令人郁悶的是,我們的老闆反複無常,經常調整員工的工資。如果他心情好,就可能把每位員工的工資加上一個相同的量。反之,如果心情不好,就可能把他們的工資扣除一個相同的量。我真不知道除了調工資他還做什麼其它事情。 工資的頻繁調整很讓員工反感,尤其是集體扣除工資的時候,一旦某位員工發現自己的工資已經低于了合同規定的工資下界,他就會立刻氣憤地離開公司,并且再也不會回來了。每位員工的工資下界都是統一規定的。每當一個人離開公司,我就要從電腦中把他的工資檔案删去,同樣,每當公司招聘了一位新員工,我就得為他建立一個工資檔案。 老闆經常到我這邊來詢問工資情況,他并不問具體某位員工的工資情況,而是問現在工資第k多的員工拿多少工資。每當這時,我就不得不對數萬個員工進行一次漫長的排序,然後告訴他答案。 好了,現在你已經對我的工作了解不少了。正如你猜的那樣,我想請你編一個工資統計程式。怎麼樣,不是很困難吧?
輸入
輸出
輸出檔案的行數為F指令的條數加一。 對于每條F指令,你的程式要輸出一行,僅包含一個整數,為目前工資第k多的員工所拿的工資數,如果k大于目前員工的數目,則輸出-1。 輸出檔案的最後一行包含一個整數,為離開公司的員工的總數。
樣例輸入
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
樣例輸出
10
20
-1
2
提示
I指令的條數不超過100000
A指令和S指令的總條數不超過100
F指令的條數不超過100000
每次工資調整的調整量不超過1000
新員工的工資不超過100000
題目:http://www.zybbs.org/JudgeOnline/problem.php?id=1503
分析:這題用到幾乎所有SBT的操作,感覺挺适合用來熟悉SBT這個資料結構的,這題隻要注意加減所有成員的工資開個變量統計,新來的員工先減掉目前的變量值再加入,新來的成員也要先判斷一下是否滿足條件再加入(雖然不知道資料有沒有這麼囧)
代碼:
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=1111111;
int L[mm],R[mm],S[mm],V[mm];
int i,j,k,n,limit,tt,root,add,sum,ans;
char C;
void Right_Rotate(int &t)
{
int k=L[t];
L[t]=R[k];
R[k]=t;
S[k]=S[t];
S[t]=S[L[t]]+S[R[t]]+1;
t=k;
}
void Left_Rotate(int &t)
{
int k=R[t];
R[t]=L[k];
L[k]=t;
S[k]=S[t];
S[t]=S[L[t]]+S[R[t]]+1;
t=k;
}
void maintain(int &t,bool flag)
{
if(flag)
if(S[R[R[t]]]>S[L[t]])Left_Rotate(t);
else if(S[L[R[t]]]>S[L[t]])
Right_Rotate(R[t]),Left_Rotate(t);
else return;
else
if(S[L[L[t]]]>S[R[t]])Right_Rotate(t);
else if(S[R[L[t]]]>S[R[t]])
Left_Rotate(L[t]),Right_Rotate(t);
else return;
maintain(L[t],0);
maintain(R[t],1);
maintain(t,0);
maintain(t,1);
}
void Insert(int &t,int v)
{
if(t)
{
++S[t];
if(v<V[t])Insert(L[t],v);
else Insert(R[t],v);
maintain(t,v>=V[t]);
}
else
{
S[t=++tt]=1;
V[t]=v;
L[t]=R[t]=0;
}
}
int Delete(int &t,int v)
{
--S[t];
if(v==V[t]||v<V[t]&&!L[t]||v>V[t]&&!R[t])
{
int tmp=V[t];
if(!L[t]||!R[t])t=L[t]+R[t];
else V[t]=Delete(L[t],V[t]+1);
return tmp;
}
else if(v<V[t])return Delete(L[t],v);
else return Delete(R[t],v);
}
int Find(int t,int v)
{
while(t&&v!=V[t])
t=v<V[t]?Find(L[t],v):Find(R[t],v);
return t;
}
int Rank(int t,int v)
{
if(!t)return 1;
if(v<=V[t])return Rank(L[t],v);
else return S[L[t]]+1+Rank(R[t],v);
}
int Select(int t,int k)
{
if(k==S[L[t]]+1)return V[t];
if(k<=S[L[t]])return Select(L[t],k);
else return Select(R[t],k-1-S[L[t]]);
}
int Pred(int t,int v)
{
if(!t)return v;
if(v<=V[t])return Pred(L[t],v);
else
{
int tmp=Pred(R[t],v);
return tmp==v?V[t]:tmp;
}
}
int Succ(int t,int v)
{
if(!t)return v;
if(v>=V[t])return Succ(R[t],v);
else
{
int tmp=Succ(L[t],v);
return tmp==v?V[t]:tmp;
}
}
int main()
{
scanf("%d%d",&n,&limit);
ans=sum=add=root=tt=S[0]=0;
for(i=0;i<n;++i)
{
while((C=getchar())<'A'||C>'Z');
scanf("%d",&k);
if(C=='I'&&k>=limit)Insert(root,k-add),++sum;
if(C=='A')add+=k;
if(C=='S')
{
add-=k;
while(sum&&(j=Select(root,1))+add<limit)Delete(root,j),--sum,++ans;
}
if(C=='F')
if(k>sum)puts("-1");
else printf("%d\n",Select(root,sum-k+1)+add);
}
printf("%d\n",ans);
return 0;
}