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


ソース: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)
    関連問題も木を切ることと変わらない.説明は省略します.