[コードテスト]小遣い管理

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

もんだいぶんせき

まず,時間制限は1秒,メモリ制限は128 MB,N制限は100000である.
もちろん、O(N 2)O(N^2)O(N 2)の使用は許されず、O(Nlogn)O(Nlogn)O(Nlogn)複雑度の使用のみが許される.従って,この問題は二分探索によって解決できる.
今、戦略を立てましょう.

どうやって解くの?

私たちが探しているのは、賢宇が毎回抽出する金額の最大値で、この探索を通じて求めなければならないことです.
しかし、賢宇が引き出す金額には条件がある.賢宇が使用した金額の最値以上であるべきだ.なぜなら、抽出する金額が使用する金額より小さい場合は、費用を抽出および使用できません.
したがって、これらのユーザのナビゲーションに上記の条件を含める必要があります.

コードを確認しながら説明

import sys

input = sys.stdin.readline

# 6236 용돈관리
N, M = map(int, input().split())
money_list = []

for _ in range(N):
    tmp = int(input())
    money_list.append(tmp)
    
balance = 0
start, end = min(money_list), sum(money_list)
mid = 0

while start <= end:
    mid = (start + end) // 2
    count = 1
    balance = mid
    
    for money in money_list:
        if balance < money:
            balance = mid
            count += 1
        balance -= money
            
    if count > M or mid < max(money_list):
        start = mid + 1
    else:
        end = mid - 1
        
print(start)

初めてホワイトゲートに入るときはお金を抜いてから始めますお金を引いたので、残高にはmidしか残っていません.countは1です.
次にfor文に入り、使用する金額リストを線形にナビゲートします.残高が不足している場合は、残高を記入しcount 1を増やしてください.
お金が十分であれば残高からお金と同じくらいの金額を減らせばいいのでしょうか?
また、最後にcount>Mであれば抽出金額が小さいことを示すため、startを大きくして抽出金額を大きくする.midが足りなくてもstartを育てます.
逆にendを小さくすることで、引き出し金額の大きさを小さくすることができます.
これにより、出力startが問題を解決します.
上記の解決策では、startをmin(mone list)に設定し、max(mone list)に設定するのが私が説明した最適な解決策です.
それでもminとの複雑さはあまり変わらないので成功しましたがmaxを使えばもっと良い答えになります!