CodeForces - 1077D Cutting Out （二分）

???? ???? ????
纪念一下自己又忘了二分这个算法，我好傻QAQ，太久不写，简直像康复训练

map<int,int>mp;
set<int>s;
vector<pii>v;
vector<pii> ans,res;
int n,k;
int check(int mid)
{
    ans.clear();
    int tmp=k;
    for(auto x:v)
    {
        int mx=min(tmp,x.first/mid);
        ans.push_back(make_pair(mx,x.second));
        tmp-=mx;
        if(tmp<=0) break;
    }
    if(tmp<=0) return 1;
    else return 0;
}
void solve()
{
    cin>>n>>k;
    rpp(i,n) 
    {
        int x;cin>>x;
        ++mp[x];
        s.insert(x);
    }
    for(auto x:s) v.push_back(make_pair(mp[x],x));
    sort(lla(v));
    int l=1,r=n/k;//删减数组的次数
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            l=mid+1;
            res=ans;
        }
        else r=mid-1;
    }
    for(auto x:res)
    {
        rpp(i,x.first) cout<<x.second<<" ";
    }
    cout<<endl;
}
signed main()
{
    solve();
    stop;
    return 0;
}