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 +1+1，而后面的会+ 1 +1+1，所以如果只看目前出现次数多于1 11的最小的数字x xx， 总有一个x xx会被单独留下来，其他的x xx会继续上升。由于比x xx小的数都只出现最多一次，所以它们不会上升，不会使数字x xx的出现次数因它们的上升增加。每次操作都会使至少一个新的数字的出现次数变成1 11：1 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次操作。

#include<bits/stdc++.h>#pragmaGCCoptimize("O3,unroll-loops")#pragmaGCCtarget("avx2,bmi,bmi2,lzcnt,popcnt")usingnamespacestd;#definelllonglong#defineendl'\n'intt,n,k,cnt[400005],a;voidclean(){for(inti=1;i<=2*n;i++)cnt[i]=0;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--){cin>>n>>k;clean();for(inti=1;i<=n;i++)cin>>a,cnt[a]++;intans=0,cntt=0,step=0;for(inti=1;i<=2*n;i++){if(cnt[i]==0){if(cntt==0)continue;if(cntt>k){cntt--;step++;}else{ans=max(ans,step);cntt=0;step=0;}}else{cntt+=cnt[i];if(cntt>k){cntt--;step++;}else{ans=max(ans,step);cntt=0;step=0;}}}if(cntt>k)step+=cntt-k;ans=max(ans,step);cout<<ans<<endl;}return0;}