Edit

【pythonでABC174を解説】E - Logs

問題概要

問題ページ

問題文

丸太が \(N\) 本あり、それぞれ長さは \(A_1,A_2,\cdots,A_N\) です。

これらの丸太を合計 \(K\) 回まで切ることができます。
長さ \(L\) の丸太を片端から \(t (0<t<L)\) の位置で切ると、長さ \(t,L-t\) の丸太に分かれます。

丸太を合計 \(K\) 回まで切った後最も長い丸太の長さが最小でいくつになるか求め、小数点以下を切り上げた値を出力してください。

制約

  • \(1 \leq N \leq 2 \times 10^5\)
  • \(0 \leq K \leq 10^9\)
  • \(1 \leq A_i \leq 10^9\)
  • 入力はすべて整数である。

問題の考察

ACコード

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))

    cor_v = 10 ** 20
    inc_v = 0
    while cor_v - inc_v > 1:
        bin_v = int((cor_v + inc_v) / 2)
        cost = 0
        for v in a:
            cost += (v + bin_v - 1) // bin_v - 1
        if cost <= k:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()

 

プログラミング

-Edit
-