Yukicoder067 よくある棒を切る問題(1)

問題概要

ユキさんは$N$本の棒を持っていて、$i$番目の棒の長さは$L_i$です。
棒は(長さを分割する方向に)自由に切ることができますが、繋げることはできません。
ユキさんは同じ長さの$K$本の棒を作りたいのです。
作れる$K$本の棒の長さの最大値を求めるプログラムを書いて下さい。

$N\leqq2*10^5$、$L_i\leqq10^9$、$K\leqq10^{10}$

yukicoder067

解法

$f(x)$:=長さ$x$の棒を$K$本以上作れるかとすると小さい$x$について連続して成立する性質があるので、これを二分探索する。

計算量:$O(NlogK)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VL = vector<LL>;        using VVL = vector<VL>;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    bool f(double x, LL K, VL& L) {
        LL ret = 0;
        FOR(i, 0, SZ(L)) {
            ret += L[i] / x;
        }
        return ret >= K;
    }
    LL N;
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VL L(N);
        FOR(i, 0, N) {
            cin >> L[i];
        }
        LL K; cin >> K;
        double ok = 0; double no = 1e11;
        FOR(i, 0, 100) {
            double mid = (no - ok) / 2 + ok;
            if (f(mid, K, L)) {
                ok = mid;
            }
            else
                no = mid;
        }
    
        double ans = ok;
        cout << fixed << setprecision(10) << ans << "\n";
    
        return 0;
    }