Codeforces Round 1066 E Adjusting Drones [CF 2157 E] O(n) 解法

原题题意有一个数组a aa长度为n nn你的目标是使每个数字在数组中的出现次数都不超过k kk。当有任何一个数字的出现次数超过k kk的时候就会执行以下操作对于a i a_iai​如果有一个数在数组中排在a i a_iai​前面并且与a i a_iai​相等则让a[i]。举个例子1 2 1 2 2在一次操作后会变成1 2 2 3 3。第一个1 11前面没有和它一样的数不变第二个是2 22前面也没有和它一样的数。第三个是1 11前面有一个1 11在数组的第一个 了所以它变成2 22第四个是2 22前面有一个2 22在数组第二个 了所以它变成3 33。思路先来看一下需要几次操作才能使每个数字出现次数都是1 11。由于每次操作时同一个数字中排在最前面的都不会 1 11而后面的会 1 11所以如果只看目前出现次数多于1 11的最小的数字x xx 总有一个x xx会被单独留下来其他的x xx会继续上升。由于比x xx小的数都只出现最多一次所以它们不会上升不会使数字x xx的出现次数因它们的上升增加。每次操作都会使至少一个新的数字的出现次数变成1 111 1 2 2 1 3 3 - 1 2 2 3 2 3 3(1 is alone) - 1 2 3 3 3 4 4(2 is alone)故操作次数至多为n nn。我们考虑一个数组1 2 2 1 1 5 6 6 5 3。记录每个数字在数组中出现的下标观察它们如何变化。黑色是数字蓝色是每个数字初始的时候在数组中出现的下标紫色表示成为了这个数字的最小下标此轮不移动绿色表示这些下标上的数字变化了。每次操作就是确定一个数字的最小坐标留在原地然后剩下的坐标全都往下移给更大的数字。数字一定是不断上升的我们尝试按照数字从小到大来看。这里数字用1数组下标用1 11。首先是1有1这个数字的最小下标是1 11所以1 11扔掉反正后面也用不到了。然后把4 44和5 55交给2处理。然后看2目前所有下标里最小的是2 22所以2 22扔掉3 33还有刚才1给我们的4 44和5 55交给3处理。到3这里目前最小的坐标是2刚刚给我们的3 33所以3 33扔掉4 , 5 , 10 4,5,104,5,10给4。就这样一直做下去。为什么可以按照数字对齐呢一起移动的时候就算是有一个数字的坐标跑在前面后来也会停下来直到一个更小的数字的坐标遇到了停在那里的它然后它才又开始走还不如我们让它先等着然后再和后面撞到它的下标齐头并进一起往前走。反正怎么也不会落了它。如果你说它如果晚点开始走不会影响比它大的数字的移动吗因为它本来应该到那个更大的数字的时候却没有到。其实一点影响也没有它先和后面那个大数字跑多远都没用还是要停下来等后面的小数字慢慢往前挪。那如果考虑到一个数字的时候发现下标的数量已经小于等于k kk了呢那就停止也不用把这一层的下标传给下一个数字了。然后继续枚举直到出现次数太多的数字再继续移动。有些读者就想了只要有多于一个的同一种数字整个操作没结束都是必须要继续移动的吧还能想留着就留着其实移不移根本无所谓虽然我们没有同时考虑但是比这个数字大的数字和小数字其实是同时移动的每次都一步小的数字怎么挪都追不上大数字的大部队而且它们已经满足条件了继续往下移也不会超过k kk所以不移动小数字不影响判断。我们最终的答案就是每段的挪移步数的最大值。这些移动的部分都互不干扰上面已经解释过小数字一但出现次数小于等于k kk就没必要移了也不会再给更大的数字添累赘的结论。为了使实现更简单我们其实不需要知道当前考虑的数字的最小下标也不需要知道这个数字具体有什么下标因为移动哪个下标其实都无所谓只要知道下标的数量就好了然后程序就变得非常非常简单。实现维护三个变量c n t t cnttcntt是当前这个数字有多少个下标s t e p stepstep是当前这一段已经操作了几次a n s ansans负责记录s t e p stepstep的最大值。扫完2 n 2n2n个数字之后如果2 n 2n2n的出现次数超过k kk还需要继续向上加数值每加一出现次数就减一所以还需要c n t t − k cntt-kcntt−k次操作。#includebits/stdc.h#pragmaGCCoptimize(O3,unroll-loops)#pragmaGCCtarget(avx2,bmi,bmi2,lzcnt,popcnt)usingnamespacestd;#definelllonglong#defineendl\nintt,n,k,cnt[400005],a;voidclean(){for(inti1;i2*n;i)cnt[i]0;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cint;while(t--){cinnk;clean();for(inti1;in;i)cina,cnt[a];intans0,cntt0,step0;for(inti1;i2*n;i){if(cnt[i]0){if(cntt0)continue;if(cnttk){cntt--;step;}else{ansmax(ans,step);cntt0;step0;}}else{cnttcnt[i];if(cnttk){cntt--;step;}else{ansmax(ans,step);cntt0;step0;}}}if(cnttk)stepcntt-k;ansmax(ans,step);coutansendl;}return0;}