SRM 204 DIV1 Hard WorldPeace

問題 Editorial

問題

数列countriesと数値kが与えられる。
[0,|countries|)の中から重複なしでkつ選んだものの数を最大化せよ。
ただし、iはcountries[i]個までしか使えない。

• 2<=k<=20
• k<=|countries|<=50
• 1<=countries[i]<=10^9

解答

Editorialを読んだ。
単純に作る数を二分探索すればよい。
判定は(Sum {min(m, countries[i])} >= m*k)という単純なもの

コメント

非常に簡単な解答。しかし思いつけなかった。
考えたのはgreedyを高速化する方法で、これはEditorialでも「駄目な複雑な考え方」としてたくさんの人がそうしていたと書いてあった。
まず、二分探索が考える段階で一度も考えてないことが駄目だ。二分探索は常に考えよう

コード

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
using namespace std;
typedef long long ll;

struct WorldPeace {
	long long numGroups(int k, vector <int> c) {
		ll l = 0, u = 100000000000LL;
		while(u-l > 1) {
			ll m = (l+u) / 2;
			ll x = 0;
			rep(i, c.size()) {
				if(c[i] > m) x += m;
				else x += c[i];
			}
			if(x >= k * m) l = m;
			else u = m;
		}
		return l;
	}
};