题目链接:http://codeforces.com/contest/1077/problem/D
题意是输入n个数,然后输入一个k,要求从n个数中任意选出k个数,使得这些数的出现次数相同且最大。
二分出现的最大次数,然后去判断是否可行,因为有些数出现次数可能是k的倍数,所以要有一个除法的操作,不难理解...
AC代码:
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int n, m, xx;
int pre[maxn];
bool solve(int limit){
int sum = 0;
for(int i=1;i<maxn;i++){
if(pre[i] >= limit){
sum += pre[i] / limit;
if(sum >= m)return true;
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&xx);
pre[xx] ++;
}
int l = 1, r = n, mid;
int ans = 1;
while(l <= r){
mid = (l + r) >> 1;
if(solve(mid)){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
vector<int> v;
int flag = 0;
for(int i=1;i<maxn;i++){
if(pre[i] >= ans){
for(int j=1;j<=pre[i]/ans;j++){
v.push_back(i);
if(v.size() == m){
flag = 1;
break;
}
}
if(flag) break;
}
}
for(int i=0;i<v.size();i++){
printf("%d ",v[i]);
}
return 0;
}