本文主要是介绍codeforces 999D Equalize the Remainders，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：点击打开链接
题意：给你一个含有n个整数的数组a1,a2,…,an，和一个正整数m。保证m是n的因数。 在单次移动中，你可以选择在1到n之间的任一位置的数ai加1. 计算cr（0~m-1）——每个元素除以m之后的余数r。换句话说，对于每个余数， 找到与它相对应的元素。 你的任务是改变数组的元素使得c0=c1=…=cm-1=n/m; 找到满足上述要求的最小的需要改变的次数 。
分析：贪心，首先记录每个取余m后的结果数的个数，如果个数不大于n/m则不用改变，否则（需要改变）插入set，然后二分查找出大于该数的且余数个数小于n/m的数，把数组变化，同时更新对应值。注意如果找不到大于该数的且余数个数小于n/m的数，就是小于它的第一个数。具体细节见代码。主要熟悉了set和auto的用法。后又参考大佬的代码，他是边读边处理的结果是一样的。代码能力还有待提高啊。
我的代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define eps 1e-10
const int N = 3e5+10;ll n,m,cnt[N],tp[N];
ll a[N];int main() {ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;ll k=n/m;for(int i=1;i<=n;i++) {cin>>a[i];cnt[a[i]%m]++;}set<ll> s;for(ll i=0;i<m;i++)if(cnt[i]<k) s.insert(i);ll ans=0;for(ll i=1;i<=n;i++) {if(cnt[a[i]%m]<=k) continue;auto it=s.lower_bound(a[i]%m);if( it!=s.end() ) {ans += (*it-a[i]%m);cnt[a[i]%m]--;cnt[*it]++;a[i]+=(*it-a[i]%m);if(cnt[*it]>=k) s.erase(*it);}else {ans += (m-(a[i]%m-*s.begin()));cnt[a[i]%m]--;cnt[*s.begin()]++;a[i]+=(m-(a[i]%m-*s.begin()));if( cnt[*s.begin()]>=k) s.erase(*s.begin());}}cout<<ans<<endl;for(int i=1;i<=n;i++){cout<<a[i];if(i!=n) cout<<" ";}return 0;
}大佬的代码：
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
const int N=2e5+6;
set<ll>st;
//cnt数组用来存0~m-1位置的所有的余数的个数都为n/m
//arr数组用来存输入的数组，以及改变后的数组
//res用来存当前值的余数
//val用来存应该最优应该选取的余数的值。
//ans用来存需要改变的操作数
ll n,m,cnt[N],arr[N],res,val,ans;
int main(){cin>>n>>m;for(int i=0;i<m;cnt[i++]=n/m)st.insert((ll)i);for(int i=0;i<n;i++){cin>>arr[i];res=arr[i]%m;//贪心部分 if(res>*st.rbegin())val=*st.begin(); else val= *st.lower_bound(res);//贪心部分 ans=ans+(val-res+m)%m;if(!--cnt[val])st.erase(val);arr[i]=arr[i]+(val-res+m)%m;}cout<<ans<<endl;for(int i=0;i<n;i++)cout<<arr[i]<<" ";
}这篇关于codeforces 999D Equalize the Remainders的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
