Codeforces #380 738E. Subordinates
传送门：http://codeforces.com/contest/738/problem/E
题目翻译
有N个人，第S个人使BOSS
每个人只有一个直系上司。
现在每个人都汇报了自己的上司数量，请问最少有多少人错了。
题解
BOSS如果汇报存在上司，Ans++
如果还有其他人汇报没有上司，Ans++
接下来，把所有人汇报的上司从小到大排序，一旦汇报上司的数量出现了断层，及前一个与后一个汇报的上司数量只差大于1。
那么我们首先让之前汇报没有上司的人来填充，填充完了再让后面汇报上司最大的人来填充，这样保证了答案的最小。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; const int Maxn=2e5; int n,s; struct Worker{ int id; int sup; }; Worker wk[Maxn+5]; int Ans=0; inline bool cmp(Worker a,Worker b){ return a.sup<b.sup; } int main(){ scanf("%d%d",&n,&s); for (int i=1;i<=n;i++){ wk[i].id=i; scanf("%d",&wk[i].sup); } if (wk[s].sup!=0){ Ans++; wk[s].sup=0; } sort(wk+1,wk+n+1,cmp); int pCnt=0; for (int i=2;i<=n;i++){ if (wk[i].sup==0){ pCnt++; Ans++; }else{ break; } } int nowSup=0; for (int i=2;i<=n;i++){ if (nowSup+1>=wk[i].sup){ nowSup=max(nowSup,wk[i].sup); }else{ while(wk[i].sup-nowSup>1 && i<=n){ nowSup++; if (pCnt<=0) Ans++; if (pCnt>0) pCnt--; else n--; } nowSup=max(nowSup,wk[i].sup); } } printf("%d\n",Ans); return 0; } |
原文链接：Codeforces #380 738E. Subordinates
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!