木を切る

白駿2805

複文を用いて,バイナリ探索の方法で問題を解く.バイナリサーチは対分サーチであるため,シーケンスサーチよりもはるかに短い.しかし、タイムアウトが多すぎるため、python 3ではなくpython 3でコミットされた問題です.pypy 3がより速く実行されることを知っています.

方法重複文によるバイナリ・ナビゲーション

n, h = map(int, input().split())
# 한 줄에 여러개 받기
tree = list(map(int, input().split()))

# 자를 수 있는 나무 길이의 범위
start = 0
end = max(tree)

while(start <= end):
    
    mid = (start + end)//2 #이진탐색을 위해 반으로 쪼개기
    sum = 0
    for ele in tree:
        if ele > mid : 
            sum += ele-mid #그때그때 mid길이만큼 나무를 잘라 남은 길이의 합을 구하기
    if sum >= h: #최소 h만큼은 잘라야하기 때문에 합이 h보다 크거나 같으면
        max_h = mid #그때의 mid를 기억해준다.(반복문은 조건이 맞는 동안 계속 돌것이므로 알아서 최종 mid의 최댓값이 저장)
        start = mid + 1 #sum이 너무 크면 더 많이 잘라야하기때문에 자를 수 있는 최소 길이를 높여준다.
    elif sum < h: #sum이 너무 작으면 너무 많이 자른것이므로 자를 수 있는 최대 길이를 낮춰준다.
        end = mid - 1
print(max_h) #최대로 자를 수 있는 길이를 출력한다.

バイナリナビゲーション

二つに分かれて探求する.ステップごとの検索範囲を半分に減らし、正解に近い検索方法は、検索方法の中で非常に速いアルゴリズムです.内部のデータは、開始、中間、終了の3つの変数を使用するために整列する必要があります.
バイナリ探索の概念を学ぶとき、私はこの問題を理解しました.
https://nerogarret.tistory.com/58ここではバイナリ探索の問題についてよく説明しています.