[白俊]2805号:木を切る(Python,Pypy 3)

4741 ワード
解答白俊 テキストリンク

質問する



私の最終的な答え

n,m=map(int,input().split()) #나무의 수(n), 나무의 길이(m)
arr_h=list(map(int,input().split()))    #나무의 높이(h)

start,end=1,max(arr_h)

while start<=end: #이분탐색
    mid=(start+end)//2 #절단기의 중간값
    t=0 #자른 나무의 합을 저장할 변수
    for i in arr_h: #나무 높이 배열 접근
        if i>=mid: #나무 높이가 절단기의 중간값보다 크거나 같으면
            t=t+i-mid  #나무를 자르고, 합을 저장
    if t>=m: #자른 합이 필요한 것보다 크거나 같으면 절단기의 높이를 올림
        start=mid+1
    else:#아니라면 절단기의 높이를 낮춤
        end=mid-1
print(end)
方法
  • 点探索問題なので、中間値(mid)を求めればいいです.
  • 伐採した樹木の和が(t)に必要な長さ(m)より大きいかどうかに応じて、条件文を設定する必要がある.
  • が大きければカッターの開始位置を上げ、必要な数だけ持ち去る.
    小さい場合は、カッターの末端位置(end)を下げ、持ち運びが必要な量を増やすべきです.

    • タイムアウト?


    コミットされたコードロジックには大きな問題はありません.
    この探索問題をPythonコードで解くと、pypy 3で問題を解くのが早い題が解けるという.
    したがってpypy 3でコミットします.
    既存のコードでreadlineを使用してI/O速度を向上させようとしたが(2回目のコミット)、同様にタイムアウトが発生した.
    Python使用時
    import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000000)
    使用しているに道を教えるもあるようです.
    [Sart]Boj 10825:国営数
    226. Invert Binary Tree