[BOJ 2512]予算(Python)

6666 ワード
にぶんたんさく 白駿 テキストリンク

質問する


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)
    JarパッケージをLinux環境に公開
    [pro]ポンキモン