【ABC174】 E - Logs

atcoder.jp

解法

類題1
蟻本にのっているAOJの問題。
poj.org

類題2
典型90問の1問目。
atcoder.jp

最大値の最小化をしろということなので、二分探索を考える。
探索する条件としては、「K以下の切断回数で答えをXにできるか？」
なぜK以下でよいかというと、Kを超えない範囲で余った切断回数を使えばさらに答えを小さくすることができるためである。
切断回数の計算は、それぞれの丸太の長さを$ A_i $とすると、 $ \displaystyle \sum_{i=1}^{n}\frac{(A_i - 1)}{X} \ $ で計算できる。

実装コード

めぐる式二分探索を使って実装した。
下の記事で紹介されている。
qiita.com

void solve(long long N, long long K, std::vector<long long> A){
    long long sm = 0;
    REP (i, N) sm += A[i];

    long long ok = sm;
    long long ng = 0;
    while (ok - ng > 1) {
        long long mid = (ok + ng) / 2;

        long long cnt = 0;
        REP (i, N) {
            cnt += (A[i]-1)/mid;
        }

        if (cnt <= K) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}