首页 > 代码库 > 【Codeforces 723C】Polycarp at the Radio 贪心
【Codeforces 723C】Polycarp at the Radio 贪心
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]);}
【Codeforces 723C】Polycarp at the Radio 贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。