首页 / 更多教程 / Codeforces Round #521 (Div. 3) D. Cutting Out

Codeforces Round #521 (Div. 3) D. Cutting Out

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #521 (Div. 3) D. Cutting Out，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含977字，纯文字阅读大概需要2分钟。

内容图文

D. Cutting Out

题目链接：https://codeforces.com/contest/1077/problem/D

题意：

给你n个数，现在要你选k个数出来，并且能够从这n个数种选取尽量多的这k个数。

 

题解：

一开始想的贪心+模拟，然后写崩了...

其实这个题二分一下选几组就好了，因为要选几个数是固定了的，所以我们可以用二分来判断可行性（根据二分的x和每个数出现的次数来判断），即是否可以选够k个数，这个很容易办到。

然后最后统计一下每个数出现的个数，最后无脑选输出答案就行了。

 

代码如下：

#include <bits/stdc++.h>
usingnamespace std;
typedef longlong ll;
constint N = 2e5+5;
int n,k;
int s[N],cnt[N];
vector <int> ans;
bool check(int x){
    ans.clear();
    for(int i=1;i<=N-5;i++){
        if(!cnt[i]) continue ;
        int need = min(cnt[i]/x,k-int(ans.size()));
        for(int j=1;j<=need;j++) ans.push_back(i);
        if(ans.size()==k) returntrue;
    }
    returnfalse;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        cnt[s[i]]++;
    }
    int l=1,r=N,mid;
    int re;
    while(l<r){
        mid=l+r>>1;
        if(check(mid)){
            l=mid+1;
            re=mid;
        }else r=mid;
    }
    check(re);
    for(auto v:ans) printf("%d ",v);
    return0;
}

 

原文：https://www.cnblogs.com/heyuhhh/p/10294398.html

内容总结

以上是互联网集市为您收集整理的Codeforces Round #521 (Div. 3) D. Cutting Out全部内容，希望文章能够帮你解决Codeforces Round #521 (Div. 3) D. Cutting Out所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1213454.html

来源：【匿名】