木を切る

質問する

尚根は木Mメートルが必要です.近くで木を買う場所が壊れてしまったので、政府に伐採許可を申請しました.政府は尚勤があなたの家の近くの木を伐採することを許可し、尚勤は新しく買った木材切断機を使って木を救う.
木材切断機の動作は以下の通りです.まず、尚根はカッターに高さHを指定しなければならない.高さを指定した後、のこぎりは地面からHメートルまで登った.そして、一連の木を切り落とす.そのため、高さがHより大きい木は、H上の部分は切り落とされ、低いものは切り落とされません.例えば、1行連続した木の高さは20,15,10,17である.尚根が高さ15を指定すると、木を切った後の高さは15、15、10、15になりますが、尚根は5インチの木と2インチの木を持って家に帰ります.(合計7メートル)カッターで設定できる高さは正の整数またはゼロです.
尚根は環境に興味があるので、どれだけの木を家に持ち帰るかだけを考えていた.このとき、少なくともmメートルの木を持ち帰るために、カッターが設定できる高さの最値を求めるプログラムを作成してください.

入力

1行目は、木の数Nと、上根が持ち帰ろうとする木の長さMを与える.(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
2行目はツリーの高さを示します.木の高さの和はいつもM以上なので、常根はいつも家に必要な木を持っていくことができます.高さが10000000以下の整数または0.

しゅつりょく

少なくともmメートルの木を家に持ち帰るために、設定可能な高さの最値をカッターに出力します.

入力例1

4 7
20 15 10 17

サンプル出力1

15

入力例2

5 20
4 42 40 26 46

サンプル出力2

36

問題を解く

n,m=map(int,input().split())
tree=list(map(int,input().split()))

left=0
right=max(tree)
answer=0

while left<=right:
    ans=0
    mid=(left+right)//2
    for t in tree:
        if t>=mid:
            ans+=t-mid
            # 이 부분을 넣기 전에는 시간초과가 발생했다.
            if ans>m:
                break
    if ans<m:
        right=mid-1
    else:
        left=mid+1
        answer=mid
print(answer)

樹木が全て伐採される場合もあるので、0から나무의 최대값の範囲内で、mの値と等しいかやや大きい値を求める必要がある.
木を切る長さがm値に等しいとは限らないから!
樹高からmidを引いた値は上根が取れる木の長さであるため,その値が上根が望むmの値と等しいかどうかを比較し,二分探索を行った.
木の高さからmidを差し引いた値はmの値より大きくてもよいが、小さくてはならない.mより短い木は持って行けません.if문からmなら、縛ってください.
上記のコード注釈においても、midを基準として切り出すと、上根が取得できる木の長さはmよりも大きくなる.
途中でbreakをしないとタイムアウトが発生します.
いずれにしてもmより長いと、それより小さい値を探索しなければならないので、以降の計算は不要で、時間の無駄になるだけです.
最初はこの事実を思いもよらず、二分探索コードを作っただけで、無条件にm値が同じ場合にbreak値を印刷したが、答えが間違っていて、また思い出した.
もう一度考えてから答えたほうがいいです.

他人を解く

N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree)

while start <= end:
    mid = (start+end) // 2
    
    log = 0
    for i in tree:
        if i >= mid:
            log += i - mid
    
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)

タイムアウトが発生したコードと同じように、何が違うのか調べてみました.
以上のコードは、pythonを回転するのではなく、Pypy3を回転するコードです.Pypy3は初めて聞いたことがありますが、JITコンパイラでpythonよりも早い言語に改良されています.しかし、メモリを使うデメリットも多い.

単純コードを変換する場合、pythonが有利、

が有利

の複雑なコードを変換する場合、pypy3が有利であると言われています.

注https://www.pypy.org