[BOJ 2512]予算(Python)

質問する

https://www.acmicpc.net/problem/2512

国家予算の上限を超えないことを確定し、
予算請求の和を求める問題💰

問題を解く

二分探索範囲

を決定する

l, r = goal // n, max(moneys)

goalは総予算で、nは地方用水です.
最高価格lは、総予算を地方の数で割る.
最低価格のrは、受け取った申請予算の中で最大の1つです.

上限チェック関数宣言

def checking(highest_m):
    hap = sum(highest_m if highest_m < m else m for m in moneys)
    return hap

mones配列の要素に상한값보다 큰 값がある場合は、상한값が加算されます.상한값보다 작은 값であれば、그 요소を加えます.

関数の戻り値で

を比較する.

if checking(mid) > goal:
    r = mid - 1
else:
    answer = max(answer, mid)
    l = mid + 1

関数の戻り値が目標予算より大きい場合は、rを小さくします.
(r減少=mid減少=上限減少)
戻り値が目標予算以下の場合
現在の上限値と答え変数を比較して、より大きな値を得ます.
そしてlを増やします.
(l増加=mid増加=上限増加)

コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
moneys = list(map(int,input().rsplit()))
goal = int(input())

def checking(highest_m):
    hap = sum(highest_m if highest_m < m else m for m in moneys)
    return hap

l, r = goal // n, max(moneys)
answer = 0
while l <= r:
    mid = (l + r) // 2
    # 더한 금액이 goal보다 같거나 크므로 상한액 줄여주기
    temp = checking(mid)
    #print("answer:{0}, mid:{1}, l:{2}, r:{3}".format(temp,mid,l,r))
    if checking(mid) > goal:
        r = mid - 1
    else:
        answer = max(answer, mid)
        l = mid + 1

print(answer)