題目鏈接：點擊查看

題目大意：給出一個數(shù)列 a ，現(xiàn)在有兩種操作：

找到一個最小值，使其值加一

找到一個最大值，使其值減一

注意這里找到一個最值進行的操作，是針對最值不唯一的情況，題目問至少需要進行多少次操作，可以使得某個數(shù)字出現(xiàn)的次數(shù)大于等于 k 次

題目分析：一道不知道為什么放在F題的F題。。因為E題卡了半個小時最后還沒解決掉，還剩十分鐘結(jié)束比賽的時候看到群友說F題是模擬，抓緊時間去讀題，讀完題后感覺還算蠻簡單的，稍微寫了寫調(diào)了一下，補題的時候交上去直接就A了，有種上當(dāng)了的感覺

因為兩種操作無非是從最小值往上一直加一，或者是從最大值一直往下減一，不難想到前綴和，所以這里我定義四個數(shù)組：

cnt[ i ]：從最小值開始到值為 i 的數(shù)為止(包括 i )，共有多少個數(shù)

inv_cnt[ i ]：從最大值開始到值為 i 的數(shù)為止(包括 i )，共有多少個數(shù)

sum[ i ]：將小于值為 i 的數(shù)都變成 i 所需要的操作數(shù)

inv_sum[ i ]：將大于值為 i 的數(shù)都變成 i 所需要的操作數(shù)

這里單獨講一下 cnt 數(shù)組和 sum 數(shù)組的轉(zhuǎn)移方程，inv_cnt 和 inv_sum 大同小異，這里就不展開說了

cnt 數(shù)組就是一個單純的前綴和：cnt[ i ] = cnt[ i - 1 ] + num[ i ] ，num數(shù)組是值為 i 的數(shù)出現(xiàn)了幾次

sum 數(shù)組的轉(zhuǎn)移需要稍微想一下，需要借助 cnt 數(shù)組，不是很難：sum[ i ] = sum[ i -1 ] + cnt[ i -1 ] * 1 ，這里乘以 1 看似沒用，但是需要理解，這個 1 的實際意義是當(dāng)前數(shù)字與前一個數(shù)字之差，即 ( i ) - ( i - 1 ) = 1

到此為止，當(dāng)我們處理好了 sum 數(shù)組和 cnt 數(shù)組之后，O( n )掃一遍維護答案就好了，具體維護方法可以分情況討論一下：對于當(dāng)前的數(shù) a：

如果 num[ a ] >= k ，答案顯然為 0 ，直接退出循環(huán)輸出答案即可

如果 cnt[ a ] >= k，意思為將小于數(shù) a 的值全部變成 a 后，此時數(shù) a 的出現(xiàn)次數(shù)大于等于 k 了

如果 cnt[ a ] >= k，意思為將大于數(shù) a 的值全部變?yōu)?a 后，次數(shù)數(shù) a 的出現(xiàn)次數(shù)大于等于 k 了

將所有的數(shù)都變?yōu)閿?shù) a?

對于上面的四種情況，維護答案的最小值就好了

有一點需要注意的是，這個題目的數(shù)據(jù)范圍給的很大，也就是說需要進行離散化處理，或者可以直接用map代替離散化，代價是每次操作都有l(wèi)ogn的時間開銷，具體實現(xiàn)看代碼吧，就是上面的原理實現(xiàn)，別被復(fù)雜的stl碼風(fēng)嚇到了

代碼：
?

#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; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1328F Make k Equal(模拟)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。