ABC227D - Project Planning


【類題】

考え方

部署$i=1$から順番に,下図のように割り当てることを考える.
f:id:IsThisAPen:20211120124128j:plain:w250
考え方

すると,部署$i$のメンバーで使えるのは$\min(x, A_{i})$となる(チーム数を超えるメンバーがいると,必ずダブりが出る(鳩の巣原理)).

したがって,$x$チームを構成できる必要十分条件は

\begin{aligned}
\sum_{i=1}^{N} \min(x, A_{i})
\geq x \cdot K
\end{aligned}
である.

ある$x$までは可能で,それを超えると不可能になるという「単調性」のある問題なので,二分探索が使える.

回答例

N, K = map(int, input().split())
A = list(map(int, input().split()))

def check(team, member):
  if sum(min(a, team) for a in A) >= team * member:
    return True
  else:
    return False
  
ok = 0
ng = 10 ** 18
while ng - ok > 1:
  mid = (ok + ng) // 2
  if check(mid, K):
    ok = mid
  else:
    ng = mid
print(ok)