公式
B - 風船割りゲーム / Balloon Popping Game 解説
by
B - 風船割りゲーム / Balloon Popping Game 解説
by
sounansya
まず、投げるダーツは常に攻撃力が最大であるものとして良いです。この攻撃力を \(\displaystyle P_{\text{max}}=\max_{1\le i\le N} P_i\) とします。
また、風船を割る個数を最大化する目的下では耐久値の低い風船から順番に割っていくとして良いです。
耐久値が \(H_i\) の風船を割るために必要な操作回数は \(\displaystyle \left\lceil\frac{H_i}{P_{\text{max}}}\right\rceil=\left\lfloor \frac{H_i+P_{\text{max}}-1}{P_{\text{max}}}\right\rfloor\) です。したがって、\(H_i\) の昇順に見ていき、その風船を割ることができるかを順番に調べていけば良いです。
n, m, k = map(int, input().split())
h = list(map(int, input().split()))
p = max(map(int, input().split()))
h.sort()
ans = 0
for v in h:
k -= (v + p - 1) // p
if k < 0:
break
ans += 1
print(ans)
投稿日時:
最終更新:
