CodeForces - 1328F Make k Equal(模拟)
题目链接：点击查看
题目大意：给出一个数列 a ，现在有两种操作：
找到一个最小值，使其值加一 找到一个最大值，使其值减一注意这里找到一个最值进行的操作，是针对最值不唯一的情况，题目问至少需要进行多少次操作，可以使得某个数字出现的次数大于等于 k 次
题目分析：一道不知道为什么放在F题的F题。。因为E题卡了半个小时最后还没解决掉，还剩十分钟结束比赛的时候看到群友说F题是模拟，抓紧时间去读题，读完题后感觉还算蛮简单的，稍微写了写调了一下，补题的时候交上去直接就A了，有种上当了的感觉
因为两种操作无非是从最小值往上一直加一，或者是从最大值一直往下减一，不难想到前缀和，所以这里我定义四个数组：
cnt[ i ]：从最小值开始到值为 i 的数为止(包括 i )，共有多少个数 inv_cnt[ i ]：从最大值开始到值为 i 的数为止(包括 i )，共有多少个数 sum[ i ]：将小于值为 i 的数都变成 i 所需要的操作数 inv_sum[ i ]：将大于值为 i 的数都变成 i 所需要的操作数这里单独讲一下 cnt 数组和 sum 数组的转移方程，inv_cnt 和 inv_sum 大同小异，这里就不展开说了
cnt 数组就是一个单纯的前缀和：cnt[ i ] = cnt[ i - 1 ] + num[ i ] ，num数组是值为 i 的数出现了几次
sum 数组的转移需要稍微想一下，需要借助 cnt 数组，不是很难：sum[ i ] = sum[ i -1 ] + cnt[ i -1 ] * 1 ，这里乘以 1 看似没用，但是需要理解，这个 1 的实际意义是当前数字与前一个数字之差，即 ( i ) - ( i - 1 ) = 1
到此为止，当我们处理好了 sum 数组和 cnt 数组之后，O( n )扫一遍维护答案就好了，具体维护方法可以分情况讨论一下：对于当前的数 a：
如果 num[ a ] >= k ，答案显然为 0 ，直接退出循环输出答案即可 如果 cnt[ a ] >= k，意思为将小于数 a 的值全部变成 a 后，此时数 a 的出现次数大于等于 k 了 如果 cnt[ a ] >= k，意思为将大于数 a 的值全部变为 a 后，次数数 a 的出现次数大于等于 k 了 将所有的数都变为数 a对于上面的四种情况，维护答案的最小值就好了
有一点需要注意的是，这个题目的数据范围给的很大，也就是说需要进行离散化处理，或者可以直接用map代替离散化，代价是每次操作都有logn的时间开销，具体实现看代码吧，就是上面的原理实现，别被复杂的stl码风吓到了
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
作者：Frozen_Guardian
