codeforces 1077 D

D. Cutting Out

数字序列s先转换成不重复的数字序列，
并记录各个数字重复的次数，然后按照重复次数从大到小排序。
二分最大删除次数，最后再输出对应的序列t。参考资料

通俗解释就是，假如现在要求切7次，数字1的个数最多并且有22
那么就是1可以出现3次，那么k的值变成k-3

代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#define DEBUG(x) cout<<#x<<" = "<<x<<endl
#define id first
#define cnt second
using namespace std;
typedef pair<int,int> pii;
int n,k;
vector<pii> vec;
bool cmp(const pii p1,const pii p2)
{
    return p1.cnt>p2.cnt;
}
bool judge(int times)
{
    int t=0;
    for(int i=0;i<vec.size() ;i++ ){
        t+=vec[i].cnt/times;
    }
    return t>=k;
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&k);
    map<int,int>mp;
    for(int i=0;i<n ;i++ ){
        int t;
        scanf("%d",&t);
        mp[t]++;
    }
    for(auto e :mp)vec.push_back(e);
    sort(vec.begin(),vec.end(),cmp);
    int l=1,r=n;
    int anst=-1;
    while(l<=r){
        int tms=(l+r)>>1;
        if(judge(tms)){
            anst=tms;
            l=tms+1;
        }
        else r=tms-1;
    }
//    DEBUG(anst);
    int tk=k;
    for(int i=0;i<vec.size()&&tk>0 ;i++ ){
        int nm=vec[i].cnt/anst;
        for(int u=0;u<min(nm,tk) ;u++ ){
            printf("%d ",vec[i].id);
        }
        tk-=nm;
    }
}