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

题目链接：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;
}