[python]白駿2805:木を切る(こちらを探る)

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

方法

startを0、treesの中で最も高いツリーをmax()関数、endに設定します.treesのツリーをfor文で1つずつ取り出し、midの値と比較して切り捨てます(cut_treeに保存).
木がMよりも多く伐採されると(if cut_tree >= M)、midの値が育成されます.

"""이분탐색"""

from sys import stdin

N, M = map(int, stdin.readline().split())  # N = 나무 수, M = 집으로 가져갈 나무 길이
trees = list(map(int, stdin.readline().split()))

start, end = 0, max(trees)  # 이분탐색용 왼쪽 오른쪽 설정

while start <= end:
    mid = (start+end)//2
    cut_tree = 0  # 잘린 나무 합을 저장하기 위한 변수
    for i in trees:
        if i > mid:  # mid보다 큰 높이의 나무는 잘림
            cut_tree += i - mid

    if cut_tree >= M:  # 원하는 나무 높이보다 더 많이 잘렸다면 start에 mid+1 입력
        start = mid + 1
    else:  # 원하는 나무 높이보다 덜 잘렸다면 end에 mid-1 입력
        end = mid - 1
print(end)

課題

CPythonはタイムアウトに失敗します.改善の方法を学ばなければならない.