codeforces 999D 贪心+二分查找

D. Equalize the Remainders

You are given an array consisting of $n$ integers $a_1,a_2,\dots ,a_n$, and a positive integer $m$. It is guaranteed that $m$ is a divisor of $n$.

In a single move, you can choose any position $i$ between $1$ and $n$ and increase $a_i$ by $1$.

Let's calculate $c_r$ ($0\le r\le m-1)$ — the number of elements having remainder $r$ when divided by $m$. In other words, for each remainder, let's find the number of corresponding elements in $a$ with that remainder.

Your task is to change the array in such a way that $c_0=c_1=\cdots =c_{m-1}=\frac{n}{m}$.

Find the minimum number of moves to satisfy the above requirement.

Input

The first line of input contains two integers $n$ and $m$ ($1\le n\le 2\cdot {10}^5,1\le m\le n$). It is guaranteed that $m$ is a divisor of $n$.

The second line of input contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le {10}^9$), the elements of the array.

Output

In the first line, print a single integer — the minimum number of moves required to satisfy the following condition: for each remainder from $0$ to $m-1$, the number of elements of the array having this remainder equals $\frac{n}{m}$.

In the second line, print any array satisfying the condition and can be obtained from the given array with the minimum number of moves. The values of the elements of the resulting array must not exceed ${10}^{18}$.

Examples Input Copy 6 3 3 2 0 6 10 12 Output Copy 3 3 2 0 7 10 14 Input Copy 4 2 0 1 2 3 Output Copy 0 0 1 2 3

题意：给你n个数，每一次操作可以给某一个数加上1，每个数可以操作无数次，分成m组，每组t=n/m个数，使第一组的数膜m都等于0，使第二组数的膜m都等于1，，，使第m组的数膜m都等于m-1，每一组数可以不挨在一起。问你最少需要多少次操作才能达到目的，并输出最后完成这么多操作后的这个n数。

思路：每组t个数，先依次遍历，当当前这个数膜m的数量还小于等于t个时，直接看下一个，大于时向上找最近一个不足t个的数，这个数加上需要达到最近的这个数的需要的操作。

坑点：不知道为何，最开始的时候我用vector存那些不足t个，有t个了直接从vector里面删除，居然超时了，这题还给的3秒，最坏也是O(log(n))的复杂度，怎么可能超时，结果换成set来存一发就过了，200ms左右，难受。

代码：

#include<stdio.h> #include<string.h> #include<cmath> #include<stdlib.h> #include<time.h> #include<algorithm> #include<iostream> #include<vector> #include<queue> #include<set> #define ll long long #define qq printf("QAQ\n"); using namespace std; const int maxn=1e5+5; const int inf=2e9+1e8+1234; const ll linf=8e18+9e17; const int mod=1e9+7; const double e=exp(1.0); const double pi=acos(-1); int a[maxn<<1],b[maxn<<1]; bool use[maxn<<1]={0}; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(a,0,sizeof a); memset(b,0,sizeof b); int t=n/m; ll ans=0; //vector<int>v; //cout<<v.size()<<endl; set<int>s; set<int>::iterator iter; for(int i=0;i<m;i++) /*v.push_back(i),*/s.insert(i); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); int temp=a[i]%m; if(b[temp]<t){ b[temp]++; //if(b[temp]==t)v.erase(lower_bound(v.begin(),v.end(),temp)); if(b[temp]==t)s.erase(temp); } else { //int f=lower_bound(v.begin(),v.end(),temp)-v.begin(); iter=s.lower_bound(temp); //if(f+v.begin()==v.end()){ if(iter==s.end()){ //a[i]+=m-temp+v[0]; a[i]+=m-temp+*s.begin(); //ans+=(ll)(m-temp+v[0]); ans+=(ll)(m-temp+*s.begin()); b[a[i]%m]++; //if(b[a[i]%m]==t)v.erase(lower_bound(v.begin(),v.end(),a[i]%m)); if(b[a[i]%m]==t)s.erase(a[i]%m); } else { //ans+=(ll)(v[f]-a[i]%m); ans+=(ll)(*iter-a[i]%m); //a[i]+=v[f]-temp; a[i]+=*iter-temp; //b[v[f]]++; b[*iter]++; //if(b[a[i]%m]==t)v.erase(lower_bound(v.begin(),v.end(),a[i]%m)); if(b[a[i]%m]==t)s.erase(a[i]%m); } } } printf("%lld\n",ans); for(int i=1;i<=n;i++) if(i==n)printf("%d\n",a[i]); else printf("%d ",a[i]); } return 0; } /* 6 2 1 1 1 1 1 1 6 3 3 2 0 6 10 12 */