[AtCoder] ABC 174 E – Logs

2020年8月3日2020年12月14日

問題

方針

\( K \) 回の操作後の最も長い丸太の長さを \( t \) とします。\( t \) を固定したとき、条件を満たすかどうかを二分探索によって求めます。丸太 \( i \) の長さを \( t \) 以下にするためには、

\[ \left \lfloor \dfrac{A_i + t – 1}{t} \right \rfloor – 1\]

回切る必要があります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, K;
    cin >> N >> K;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int l = 0; int r = 1000000001;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        ll cnt = 0;
        for (int i = 0; i < N; i++) {
            if (cnt > K) break;
            cnt += (A[i] + m - 1) / m - 1;
        }
        if (cnt <= K) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << r << "\n";
    return 0;
}