codeforces 999D 贪心+二分查找

xiaoxiao2021-02-28  37

D. Equalize the Remainders

You are given an array consisting of nn integers a1,a2,,ana1,a2,…,an, and a positive integer mm. It is guaranteed that mm is a divisor of nn.

In a single move, you can choose any position ii between 11 and nn and increase aiai by 11.

Let's calculate crcr (0rm1)0≤r≤m−1) — the number of elements having remainder rr when divided by mm. In other words, for each remainder, let's find the number of corresponding elements in aa with that remainder.

Your task is to change the array in such a way that c0=c1==cm1=nmc0=c1=⋯=cm−1=nm.

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

Input

The first line of input contains two integers nn and mm (1n2105,1mn1≤n≤2⋅105,1≤m≤n). It is guaranteed that mm is a divisor of nn.

The second line of input contains nn integers a1,a2,,ana1,a2,…,an (0ai1090≤ai≤109), 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 00 to m1m−1, the number of elements of the array having this remainder equals nmnm.

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 10181018.

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 */
转载请注明原文地址: https://www.6miu.com/read-1649970.html

最新回复(0)