にぶたんの練習

Codeforces Round521 div3 D Cutting Out

問題概要

int型整数の配列sが与えられる。この配列sの中からk個の整数を選んだ配列tを配列sから取り除く。この取り除く回数が最大となる時の整数配列tを求める。なお、取り除く配列tの要素は毎回同じとし、複数答えがある場合はどれを出力してもいいものとする。

問題リンク

https://codeforces.com/contest/1077/problem/D

制約

考察

15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1

　上記のサンプルを見た時に[1,2]の組み合わせで取ると4回取れますが、[1,1]でとる場合のほうが5回取れるのでこちらの方が最適となります。
このことから一番数の少ない数字に合わせることが最適解につながらないというこどが分かります。そこで、取り除く配列tを求めるために、何回取り除けるのかを求める必要があります。h回とり除けない場合は(h+1)回とり除くことはできません。また、h回とり除ける場合は(h-1)回取り除くこともできます。このことから、取り除くことができる回数には単調性があることが分かります。よって二分探索が使えることが分かります。
　そこで、コードでは二分探索で取り除くことができる回数okを求めます。すると、配列s内の各数字について、１回の取り除く操作で取り除ける回数は回になるので、配列tに回 数字を入れます。さて、この操作を行うと配列tに k 個以上の数字が入ることになります。配列 t に入る数字がk個よりも大きい場合は、解が複数存在する場合があることを示しています。しかし、問題文にあるように、解が複数存在する場合はどれを出力してもいいため、配列tの初めの k個を出力すればいいということになります。

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<queue>
using namespace std;

#define INF 1000000000007
#define MOD 1000000007
#define ARRAY_MAX 200005

int n,k;
vector<int> a;
int cnt[ARRAY_MAX];


bool check(int middle){

	int sum = 0;
	for(int i = 0;i < ARRAY_MAX;i++){
		sum += cnt[i]/middle;
	}
	if(sum >= k){
		return true;
	}else{
		return false;
	}
}


int solve(){

	int ok = 1,ng = n;
	while(abs(ng-ok) > 1){
		int middle = (ok+ng)/2;
		if(check(middle)){
			ok = middle;
		}else{
			ng = middle;
		}
	}
	return ok;
}

int main(){

	cin >> n >> k;
	
	for(int i = 0;i < n;i++){
		int tmp;
		cin >> tmp;
		a.push_back(tmp);
		cnt[tmp]++;
	}

	int ok = solve();//ok回取り除ける

	vector<int> ans;
	for(int i = 0;i < ARRAY_MAX;i++){
		for(int times = 0;times < cnt[i]/ok;times++){
			ans.push_back(i);
		}
	}

	for(int i = 0;i < k;i++){
		cout << ans[i] << " ";
	}
	cout << endl;


    return 0;
}