Build the Fence [CSAcademy #55]

https://csacademy.com/contest/round-55/task/build-the-fence/

N本の棒があり、長さがそれぞれ分かっている。
この棒を切ることで、K本の長さが同じ棒を用意する。
用意できる最長の長さは？

N≦10^5
K≦10^14

前提知識

• 二分探索

解法

答えで二分探索する。
　
「chk(x) := 長さxの棒をK本以上用意できるか」を実装する。
これは、長さyの棒から長さxの棒は最大floor(y/x)本作ることができるため、これを集計してK本以上か判定するだけ。

typedef long long ll;
int N; ll K, A[101010];
//---------------------------------------------------------------------------------------------------
int chk(ll x) {
    ll sm = 0;
    rep(i, 0, N) sm += A[i] / x;
    return K <= sm;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K; rep(i, 0, N) cin >> A[i];

    ll ok = 0, ng = INT_MAX/2;
    while (ok + 1 != ng) {
        ll x = (ok + ng) / 2;
        if (chk(x)) ok = x;
        else ng = x;
    }
    cout << ok << endl;
}