[白俊]2805号:木を切る
4199 ワード
質問する
ツリーの高さのリストが表示されます.そして尚根が持って行きたい木の長さをあげます.ツリーのリストからツリーを選択し、ルートのカッターに高さHを指定すると、対応する高さからツリーを切ることができます.
나무 4개、持って行きたい높이가 7mの場合、20 15 10 17はい、Hが15の場合、5 0、2メートル切って持って行きます.少なくともmメートルの木を家に持ち帰るために、切断機が設定できる最高高さ値を求めるプログラムを作成してください.
どうやって解けばいいですか?
のこぎりの高さを木の最大高さに抑えると、もちろん一つも取れません.
最低の高さまで引っ張っても、切りすぎます.
最小高さと最大高さの中間からナビゲートします.そしてこの探求の概念を応用して彼を探しに行きます.
最終的には,最適数を探すためには探索を継続する必要がある.
私が犯した過ち。
😭 シェアではなく、分けました.
に答える
# 5 20
n, m = map(int, input().split())
# 4 42 40 26 46
trees = list(map(int, input().split()))
start, end = 1, max(trees) # 1, 46
result = 0
while start <= end:
mid = (start + end) // 2 # 23
cutted_tree_sum = 0
for tree in trees:
if tree > mid:
cutted_tree_sum += (tree - mid)
if cutted_tree_sum > m:
break
# cutted_tree_sum = 62
if cutted_tree_sum >= m:
start = mid + 1 # 24
result = mid # 23
else:
end = mid - 1
print(result)
Reference
この問題について([白俊]2805号:木を切る), 我々は、より多くの情報をここで見つけました https://velog.io/@malza_0408/백준-2805번-나무-자르기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol