【類題】
考え方
部署$i=1$から順番に,下図のように割り当てることを考える.すると,部署$i$のメンバーで使えるのは$\min(x, A_{i})$となる(チーム数を超えるメンバーがいると,必ずダブりが出る(鳩の巣原理)).
したがって,$x$チームを構成できる必要十分条件は
\begin{aligned}
\sum_{i=1}^{N} \min(x, A_{i})
\geq x \cdot K
\end{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)