[コーディングテスト]予算
ソース:https://www.acmicpc.net/problem/2512
この問題は,従来のスクライブ,木切り問題と非常に類似した性質を持っている.したがって、以前の2つの問題を参考にすると役に立ちます.ツリーのトリム:https://velog.io/@18k7102dy/coding-test-fourth-12 クリップメッシュ:https://velog.io/@18k7102dy/coding-test-fourth-22 参考として,この問題もこの探索を利用して解決する.実は探索リストにない値のタイプはこの探索よりもっと良いものはありません...
問題を解く前に言うこと
この問題は,従来のスクライブ,木切り問題と非常に類似した性質を持っている.したがって、以前の2つの問題を参考にすると役に立ちます.
和弦から見ましょうか?
import sys
input = sys.stdin.readline
N = int(input())
budget_request_list = list(map(int, input().split()))
total_budget = int(input())
start, end = 1, max(budget_request_list)
while start <= end:
sum = 0
mid = (start + end) // 2
for budget in budget_request_list:
tmp = budget if mid >= budget else mid
sum += tmp
if sum <= total_budget:
start = mid + 1
else:
end = mid - 1
print(end)
関連問題も木を切ることと変わらない.説明は省略します.Reference
この問題について([コーディングテスト]予算), 我々は、より多くの情報をここで見つけました https://velog.io/@18k7102dy/coding-test-fourth-3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol