【Codeforces 723C】Polycarp at the Radio 贪心

饶文津

发布于 2020-06-02 10:58:05

3100

发布于 2020-06-02 10:58:05

文章被收录于专栏：饶文津的专栏饶文津的专栏

n个数，用最少的次数来改变数字，使得1到m出现的次数的最小值最大。输出最小值和改变次数以及改变后的数组。

最小值最大一定是n/m，然后把可以改变的位置上的数变为需要的数。

http://codeforces.com/problemset/problem/723/C

Examples

input

4 2
1 2 3 2

output

2 1
1 2 1 2

input

7 3
1 3 2 2 2 2 1

output

2 1
1 3 3 2 2 2 1

input

4 4
1000000000 100 7 1000000000

output

1 4
1 2 3 4

#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005];
int pos[2005],cnt;
int cha[2005];
int ans,ans2;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    ans=n/m;
    printf("%d ",ans);

    for(int i=1;i<=m;i++){
        int num=0;
        int j;
        for(j=1;j<=n;j++){
            if(a[j]==i){
                num++;
                pos[j]=1;//代表j位置不能改变
            }
            if(num==ans)break;
        }
        if(num<ans){cha[i]=ans-num;ans2+=cha[i];}
    }
    int j=1;
    for(int i=1;i<=m;i++){
        for(int k=0;k<cha[i];k++){
            while(pos[j])j++;
            a[j++]=i;
        }
    }
    printf("%d\n",ans2);
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-10-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

input