[コーディングテスト]予算

ソース:https://www.acmicpc.net/problem/2512

問題を解く前に言うこと

この問題は,従来のスクライブ,木切り問題と非常に類似した性質を持っている.したがって、以前の2つの問題を参考にすると役に立ちます.

ツリーのトリム:https://velog.io/@18k7102dy/coding-test-fourth-12

クリップ

メッシュ:https://velog.io/@18k7102dy/coding-test-fourth-22

参考として,この問題もこの探索を利用して解決する.実は探索リストにない値のタイプはこの探索よりもっと良いものはありません...

和弦から見ましょうか?

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)

関連問題も木を切ることと変わらない.説明は省略します.