P3776工資管理
時(shí)間限制 : - MS 空間限制 : 165536 KB
評(píng)測(cè)說(shuō)明 : 1000ms
問(wèn)題描述

何老板的公司有n名員工，編號(hào)1到n。一開(kāi)始所有員工的工資都是0。根據(jù)何老板的心情好壞，可能出現(xiàn)下列兩種針對(duì)員工工資的操作： 1.U x y 改工資操作：何老板將第x號(hào)員工的工資改成了y； 2.Z x y 減工資操作：何老板生氣了，他想選出x個(gè)員工，并將他們的工資全都減去1。何老板想知道，他能否一口氣進(jìn)行y次這樣的減工資操作。能輸出TAK，否則輸出NIE。注意，員工的工資不能為負(fù)。對(duì)于每個(gè)減工資的操作，何老板只是在心里想想，口頭上說(shuō)說(shuō)，嚇唬嚇唬大家，解解悶氣，他并不會(huì)真正執(zhí)行。即不會(huì)對(duì)任何人的工資進(jìn)行修改。

輸入格式

第一行包含兩個(gè)正整數(shù)n,m，分別表示員工的人數(shù)和操作次數(shù)。 接下來(lái)m行，每行一個(gè)操作，形式如題面所述。

輸出格式

包含若干行，對(duì)于每個(gè)減工資操作，若可行，輸出TAK，否則輸出NIE。

樣例輸入 1

3 8 U 1 5 U 2 7 Z 2 6 U 3 1 Z 2 6 U 2 2 Z 2 6 Z 2 1

樣例輸出 1

NIE TAK NIE TAK

樣例輸入 2

13 17 U 1 12 Z 1 9 Z 1 5 Z 4 7 U 7 18 Z 1 1 Z 1 8 U 6 4 U 1 9 U 3 13 Z 5 2 U 7 8 U 4 20 U 7 14 Z 6 1 Z 3 2 Z 8 7

樣例輸出 2

TAK TAK NIE TAK TAK NIE NIE TAK NIE

提示

對(duì)于30%的數(shù)據(jù)：1<=n,m<=1000 對(duì)于100%的數(shù)據(jù)：1<=n,m<=200000 1<=x<=n，0<=y<=10^9，1<=y<=10^9。

來(lái)源 改編自POI2015 Logistyka

沒(méi)想到老板的公司竟然有高達(dá)20萬(wàn)個(gè)員工

題解

思路

分析下題意

對(duì)于這道題目，我們大概可以分析出

當(dāng)扣錢次數(shù)為y次時(shí)，一個(gè)人最多被扣掉y塊錢 所以對(duì)于工資>y的人，他最多也就只能被扣y塊錢（最多被扣y次） 對(duì)于工資<=y時(shí)，他最多就被扣完

而且對(duì)于一個(gè)扣款y，因?yàn)樗欠謞次扣的，所以可以被扣在多個(gè)人頭上（這個(gè)結(jié)論應(yīng)該是很容易想到的，不作證明）

所以我們就可以分析出結(jié)果

對(duì)于工資大于y的人，我們記錄他被扣的錢為y元 而工資小于y的人，我們就把他的錢扣完

舉例

假設(shè)修改后工資為 1 2 5 7 8 6 3 2 1如果老板的要求是,5個(gè)人,扣4次 所以一共是扣20塊錢 但由于5 7 8 6 大于4,所以這四個(gè)都算作4==>和為16 而剩下的,可以由1,2,3（工資額）一起分擔(dān) 所以,根據(jù)上面的結(jié)果來(lái)看,這個(gè)情況就是4*4(工資大于4的人)+1+2+3+2+1>4*5 所以可行換個(gè)情況 現(xiàn)在的工資總和為35 所以我們分兩種情況看①6個(gè)人,扣5次==>和為30那么一共有四個(gè)人可以扣5次這四個(gè)人的工資為(5 7 8 6)==>和為20而剩下的人工資為(1 2 3 2 1)==>和為94*5+1+2+3+2+1<5*6這種情況不行②4個(gè)人,扣8次==>和為32那么可以扣8次的人只有一個(gè)而其余的人,工資就要全部被扣光所以8*1+1+2+5+7+6+3+2+1>32所以這是可以的為什么下面這個(gè)扣款之和比上面的大,為什么下面的可以上面的卻不可以呢?? 請(qǐng)結(jié)合上面的分析進(jìn)行考慮。

解法

這道題目有兩種解法，一種是線段樹，一種是樹狀數(shù)組

先說(shuō)線段樹

這道題目一開(kāi)始我是用線段樹做的
線段樹就很簡(jiǎn)單了，基本上就是一個(gè)模板題

先把線段樹畫出來(lái),狀態(tài)定義就是 對(duì)于線段[l,r],表示的就是l號(hào)員工到r號(hào)員工的狀態(tài) 我們記錄[l,r]的工資最大值和最小值那么對(duì)于扣款次數(shù)y,如果[l,r]的最小值大于等于y,說(shuō)明[l,r]內(nèi)所有的人的工資不少于y 所以這個(gè)區(qū)間可以被扣(r-l+1)*y塊錢而對(duì)于[l,r]的最小值小于y,且最大值也小于y,就說(shuō)明[l,r]內(nèi)所有的人都不能夠被扣y次 換句話說(shuō),這些人的錢要全部被扣完 所以對(duì)這個(gè)區(qū)間我們選擇求和對(duì)于[l,r]的最小值小于y,最大值大于y 我們選擇進(jìn)行進(jìn)一步的細(xì)分討論(再把區(qū)間二分)

上面的過(guò)程其實(shí)就是一個(gè)簡(jiǎn)單的求和,唯一需要注意的是工資大于y的人在求和時(shí)只能+y

但是由于數(shù)據(jù)太過(guò)龐大,所以怎么求都要超時(shí),這種做法我們不提倡

樹狀數(shù)組

那么樹狀數(shù)組我們就不能簡(jiǎn)單地學(xué)習(xí)上面的做法了
因?yàn)槿缟鲜鲎龇ㄋ?
對(duì)于工資大于y的人,我們只能夠在求和時(shí)+y
所以樹狀數(shù)組的簡(jiǎn)單求和顯然是不行的

換個(gè)思路考慮，我們?nèi)绻修k法快速地知道有多少人的工資是大于y的,有多少人的工資是小于y的,并且能夠快速求小于y的人的工資之和,那么這樣也解決了相同的問(wèn)題。

下面我們就來(lái)依次解決上述問(wèn)題

①快速求人數(shù)
首先想到的肯定是記錄某個(gè)工資對(duì)應(yīng)的人數(shù)
但是由于工資的范圍在[0,10^9]，所以這樣肯定是要爆空間
解決辦法
我們可以記錄每個(gè)人工資的大小位置,然后對(duì)位置進(jìn)行疊加
舉例

假設(shè)每個(gè)人的工資為1 2 7 8 5 9 那么工資的大小排序1 2 4 5 3 6那么在修改時(shí)我們對(duì)工資為1的點(diǎn),我們就在位置1上加1工資為2的點(diǎn),我們就在位置2上加1工資為7的點(diǎn),我們就在位置4上加1 簡(jiǎn)言之,在修改時(shí),對(duì)工資修改是在它的大小位置上添加標(biāo)記(別忘了在原位置上減1)

那么在查詢有多少人工資比他低的人就只需要查詢它工資的位置就好
例如

上述例子中 工資 1 2 7 8 9 5 9 查詢工資比5低的人,5的位置是3,所以查詢1 2位置上的標(biāo)記個(gè)數(shù)即可

于是,對(duì)于扣除的工資數(shù)y,我們只要求出工資比y低的人數(shù),用 總?cè)藬?shù)-工資比y低的人數(shù)=工資不低于y的人數(shù)

②快速求工資小于y的人的工資總和
有了上述解法,下面的問(wèn)題就好解決了
解法
再開(kāi)一個(gè)數(shù)組,對(duì)于每次修改,在對(duì)應(yīng)位置上增加工資即可
舉例

假設(shè)每個(gè)人的工資為1 2 7 8 5 9 那么工資的大小排序1 2 4 5 3 6那么在修改時(shí)我們對(duì)工資為1的點(diǎn),我們就在位置1上加1工資為2的點(diǎn),我們就在位置2上加2工資為7的點(diǎn),我們就在位置4上加7 簡(jiǎn)言之,在修改時(shí),對(duì)工資修改是在它的大小位置上修改工資(別忘了在原位置上減去原先工資)

所以求工資小于y的人的工資總和,只要簡(jiǎn)單的在這個(gè)數(shù)組當(dāng)中求和即可

上述例子中 工資 1 2 7 8 9 5 9位置 1 2 3 4 5 6 7 標(biāo)記 1 2 5 7 8 18 (因?yàn)?的位置都是6,所以在6上記錄為9+9=18) 查詢工資比7低的人的工資之和=>位置4之前的工資之和=1+2+5=8

問(wèn)題解決

附上代碼

#include <cstdio> #include <iostream> #include <algorithm> #define lowbit(i) i&-i using namespace std;char mov[201234]; long long n,m,cnt[201234],sum[201234],to[201234],add[201234],loc[201234]={0,0},data[201234];inline int input() {char c=getchar();int o;while(c>57||c<48)c=getchar();for(o=0;c>47&&c<58;c=getchar())o=(o<<1)+(o<<3)+c-48;return o; }void ADD(int Loc,int C,int S){for(int i=Loc;i<=m;i+=lowbit(i))cnt[i]+=C,sum[i]+=S;} long long count(int Loc) {long long ans=0;for(int x=Loc;x>0;x-=lowbit(x))ans+=cnt[x];return ans; } long long SUM(int Loc) {long long ans=0;for(int i=Loc;i;i-=lowbit(i))ans+=sum[i];return ans; }int main() {//freopen("In.txt","r",stdin);//freopen("True.txt","w",stdout);scanf("%d%d\n",&n,&m);for(int i=1;i<=m;i++){mov[i]=getchar();to[i]=input();add[i]=input();loc[i]=add[i];}sort(loc+1,loc+m+2);ADD(1,n,0);for(int i=1;i<=m;i++){if(mov[i]=='U'){ADD((lower_bound(loc+1,loc+m+2,data[to[i]])-loc),-1,-data[to[i]]);ADD((lower_bound(loc+1,loc+m+2,add[i])-loc),1,add[i]);data[to[i]]=add[i];}else{int Loc=(lower_bound(loc+1,loc+m+1,add[i])-loc)-1,t=count(Loc),s=SUM(Loc);if(1LL*(n-count(Loc))*add[i]+SUM(Loc)>=1LL*add[i]*to[i])puts("TAK");else puts("NIE");}}return 0; }

順便附上對(duì)拍代碼

#include<cstdlib> #include<cstdio> #include<ctime> #include<iostream> #include<cstring>int A[123456]={987654321};using namespace std; int main() {freopen("In.txt","w",stdout);srand(time(NULL));int n=rand()%100000+1,m=rand()%100000+1;printf("%d %d\n",n,m);for(int i=1;i<=m;i++){int c=rand()%2,a=rand()%n+1,add=rand()%1000000000;printf("%c %d %d\n",(c?'U':'Z'),a,add);}return 0; }

對(duì)拍文件
運(yùn)行對(duì)拍代碼可以得到In.txt(輸入數(shù)據(jù))
運(yùn)行刪去//后的我的代碼可以得到True.txt(正解)

總結(jié)

以上是生活随笔為你收集整理的NKOJ-3776 工资管理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。