スパルタ365 5週間(3)木を切る

5339 ワード
アルゴリズム#アルゴリズム# スパルタ365 スパルタコードクラブ テキストリンク
注意:「樹木をトリムする」を参照してください。

第5週


白駿2805号は木を切ります


質問リンク:https://www.acmicpc.net/problem/2805

💡 悩む

  • の中間値
    • が見つかりました.
  • N本の木から減算値(負数面を含む)
    • を加算.
  • Mと比較する、正しければ
    • が出力される.
    -->エラー
        if sum == M:
        print(mid)
        break
    elif sum > M:
        left = mid + 1

    else:
        right = mid - 1
    ? 上記のように、中間価格が移動していくうちに、答えがないことがわかりました.

    ! 解決策


    ! 조건을 만족하는 최대의 나무 절단 높이를 찾으면 탈출한다.の条件から,Mと完全に一致しない場合が見られた.したがって、mid値ではなくright값을 출력でなければならない.
    left変化もsum>=Mであれば、すべて実現しなければならない.

    !! スキル


    .

    悟る

  • 忘れないでください:二分探索ソート後
    • を使用

    に答える

    # middle 값 찾고
# N개의 나무에서 뺀값을 더해서 (음수면 포함)
# M과 비교 후 맞으면 출력
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()
# print(trees)

left = 1
right = trees[-1]

while left<=right:
    mid = (left+right)//2
    sum = 0
    # print('mid:',mid)
    for tree in trees:
        if tree >= mid:
            sum += (tree-mid)
    if sum >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)
    コメントの作成
    nvidia-docker + caffe2 + cuda