首页 > 代码库 > 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 [贪心][乱搞]