[学習テストコード]ツリーを切る

4094 ワード
コーディングテスト にぶんたんさく テキストリンク
ソース:https://www.acmicpc.net/problem/2805

問題を解く前にまず問題を分析する


まず時間制限は1秒Nが100万まで許される状態ですもちろんアルゴリズムの複雑さがO(N^2)であれば失敗する.そのため、デュアルナビゲーションを使用して問題を解決する必要があります.

どうやって解くのか…？


まず救いたいものを明らかにしてから行きましょう.私たちが手に入れなければならないのは、鋸の最大高さを求めて、上根が少なくともmの長さの木材を得ることができるようにすることです.したがって,鋸片の長さに基づいてアルゴリズムを設計すれば十分である.

まずコードを確認しましょう。

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

height_list = list(map(int, input().split()))

start = 1
end = max(height_list)

while start <= end:
    mid = (start + end) // 2
    sum = 0
    
    for tree_height in height_list:
        tmp = 0 if tree_height <= mid else tree_height - mid
        sum += tmp
        
    if sum >= M:
        start = mid + 1
    else:
        end = mid - 1

print(end)
バイナリナビゲーションの趣旨により、startとmidの値を変更しながら範囲を縮小!
その後、対応するmid値に基づいて樹木を剪定し続け、通常、鋸片の高さが木の高さ以上である場合、樹木は剪定されないので、0を加えないと、木の高さからmidを減算してsumに反映すればよい.反論時の超能力者
sumが所望の長さより大きい場合はstartを調整できます.これは、高さをより高くすることができ、そうでない場合は高さを下げることができることを意味します.
最後に,endを出力することで問題を解決できる.
urlでファイルをローカルにダウンロード
じどうしちゅう