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<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;map<int,LL>mp,cnt,inv_cnt,sum,inv_sum;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){int num;scanf("%d",&num);mp[num]++;}auto pre=mp.begin();auto it=pre;it++;cnt[pre->first]=pre->second;sum[pre->first]=0;while(it!=mp.end())//维护 cnt 和 sum{cnt[it->first]=cnt[pre->first]+it->second;sum[it->first]=sum[pre->first]+cnt[pre->first]*(it->first-pre->first);pre=it;it++;}auto inv_pre=mp.rbegin();auto inv_it=inv_pre;inv_it++;inv_cnt[inv_pre->first]=inv_pre->second;inv_sum[inv_pre->first]=0;while(inv_it!=mp.rend())//维护 inv_cnt 和 inv_sum{inv_cnt[inv_it->first]=inv_cnt[inv_pre->first]+inv_it->second;inv_sum[inv_it->first]=inv_sum[inv_pre->first]+inv_cnt[inv_pre->first]*(inv_pre->first-inv_it->first);inv_pre=inv_it;inv_it++;}LL ans=0x3f3f3f3f3f3f3f3f;for(auto it:mp)//维护答案，四种情况{int pos=it.first;if(mp[pos]>=k){ans=0;break;}if(cnt[pos]>=k)ans=min(ans,sum[pos]-(cnt[pos]-k));if(inv_cnt[pos]>=k)ans=min(ans,inv_sum[pos]-(inv_cnt[pos]-k));ans=min(ans,sum[pos]+inv_sum[pos]-(n-k));}printf("%lld\n",ans);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1328F Make k Equal(模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。