首页 > 代码库 > Codeforces 723c [贪心][乱搞]
Codeforces 723c [贪心][乱搞]
/*不要低头,不要放弃,不要气馁,不要慌张。题意:给一个n和m。第二行给n个数。每次操作可以把n个数中的任何一个数替代为别的数,问最少的操作次数使得1.2.3.4.5...m中的数出现的次数的最小值尽可能大。输出这个数,输出最少操作次数,输出替换后的数组。思路:1.显然,最小值尽可能大,这个值是可以确定的,即n/m;2.还有,为使得操作次数最少,我们发现最多有n%m个没有贡献的无关值无需更改...3.这题实际上可以n^2复杂度,因为n只有2000.但是本渣作死,写了nloglog的复杂度...n^2复杂度的话循环检查就好...我是用一个map<int,multiset<int> >将数字的位置记录下来...然后种种... 坑:if else if else这种逻辑写崩了==仍然很弱的我逻辑逻辑逻辑*/#include<bits/stdc++.h>using namespace std;int jilu[2050],all[2050];map<int,multiset<int> >mp;int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",jilu+i); all[i]=jilu[i]; mp[jilu[i]].insert(i); } int k=n/m; int w=n%m; map<int,multiset<int> >::iterator it; multiset<int>cun; multiset<int>que; for(it=mp.begin();it!=mp.end();it++){ if(it->first <= m){ while(it->second.size()<k){ if(cun.size()){ int ss=*cun.begin(); cun.erase(cun.begin()); jilu[ss]=it->first; it->second.insert(ss); } else{ que.insert(it->first); it->second.insert(0); } } while(it->second.size() > k){ if(w>0){ w--; it->second.erase(it->second.begin()); } else if(que.size()){ int ss=*que.begin(); que.erase(que.begin()); int pos=*(it->second.begin()); it->second.erase(it->second.begin()); jilu[pos]=ss; } else{ int pos=*(it->second.begin()); it->second.erase(it->second.begin()); cun.insert(pos); } } } else{ while(it->second.size() > 0){ if(w>0){ w--; it->second.erase(it->second.begin()); } else if(que.size()){ int ss=*que.begin(); que.erase(que.begin()); int pos=*(it->second.begin()); it->second.erase(it->second.begin()); jilu[pos]=ss; } else{ int pos=*(it->second.begin()); it->second.erase(it->second.begin()); cun.insert(pos); } } } } for(int i=1;i<=m;i++){ while(mp[i].size()<k){ int ss=*cun.begin(); cun.erase(cun.begin()); jilu[ss]=i; mp[i].insert(ss); } } while(que.size()){ int pos=*cun.begin(); int ss=*que.begin(); cun.erase(cun.begin()); que.erase(que.begin()); jilu[pos]=ss; } int num=0; for(int i=1;i<=n;i++){ if(jilu[i]!=all[i])num++; } printf("%d %d\n",k,num); for(int i=1;i<=n;i++){ printf("%d ",jilu[i]); }}
Codeforces 723c [贪心][乱搞]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。