1024问

CodeForces - 1328F Make k Equal(模拟)

Tani ·
更新时间:2024-09-20
· 924 次阅读

题目链接：点击查看

题目大意：给出一个数列 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 #include #include #include using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=2e5+100; mapmp,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;ifirst]=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; }
作者：Frozen_Guardian



make CodeForces equal

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
PHP 字符串变量
Jelena 2021-04-17
886
ASP.NET之Response.Cookies.Remove 无法删除COOKIE的原因
Kefira 2020-07-10
864
详解linux 关机命令总结
Maren 2020-07-18
806
C++11 shared_ptr 与 make_shared源码剖析详解
Rose 2021-12-16
99
win10 1909蓝屏代码IRQL_NOT_LESS_OR_EQUAL怎么解决?
Mercia 2022-01-17
1809
Linux 下 Make 命令实例详解
Mathilda 2022-01-21
899
详解Linux下make命令的使用
Malinda 2022-01-25
1367
安装 unixbench make: *** [pgms/ubgears] Error 1 的解决方法
Querida 2022-01-29
1533
centos下如何安装卸载命令rpm make install?
Celandine 2022-01-31
705
Go slice切片make生成append追加copy复制示例
Netany 2022-06-13
870
浅谈Golang的new与make区别是什么
Odessa 2022-07-15
1605
Make命令基础用法教程
Kirima 2022-07-15
1896
C语言make和Makefile介绍及使用
Tertia 2022-07-15
1296
C语言Make命令用法讲解
Grizelda 2022-07-15
335
Go语言中make和new函数的用法与区别
Ula 2022-07-16
1014
Go make和new的区别是什么？
Kara 2022-07-21
1953
Linux 自动化构建工具make/Makefile的使用详解
Tani 2022-10-05
1252
深入理解Golang make和new的区别及实现原理
Nafisa 2022-11-04
1533
Linux下的自动化构建工具之make/makefile的用法详解
Ianthe 2022-11-04
331
windows下安装make及使用makefile文件
Ula 2023-01-08
1906