Yukicoder068 よくある棒を切る問題(2)

問題概要

ユウキさんは$N$本の棒を持っていて、$i$番目の棒の長さは$L_i$です。 棒は(長さを分割する方向に)自由に切ることができますが、繋げることはできません。 ユウキさんは同じ長さの棒を作りたいのですが、何本であればどのぐらいの長さにできるかが気になっています。
同じ長さの棒を$K_1,K_2,…,K_Q$ 本作るとしたら、その時の棒の長さの最大値をそれぞれ求めるプログラムを書いて下さい。

$N,Q\leqq10^5$、$L_i\leqq10^9$、$K_i\leqq5*10^5$

yukicoder068

解法

解説を見ました。
ある棒$L_i$について、これを$P$本使うとする。次使うときは$P+1$本のときで、長さも確定する。
今0本使うとして、1本使うときは集合から最大値を持ってこれば良い。
複数本作りたいときは、最大値を折るしか無い。したがって、
その後$L_i$は$L_i/($自身を使った回数+1$)$だけの長さに更新しておくと、
2本使うときの最大値は、もとの長さの$L_i$を割って2回使うあるいは、他の大きな$L_j$を使うことで得られる。
最大値の選択が解を保証するため、順番に動作を行っていけば$p$本使うときの最大値を求めることができる。
このようにして順番に$p$本使うときの長さを先に求めることでクエリ$O(1)$を達成できる。

計算量:$O(MaxK$ $logN+Q)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using LL = long long;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    struct frac {
        LL x, c;
        bool operator< (const frac& a) const {
            return a.c*x < c*a.x;
        }
    };
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        LL N; cin >> N;
        priority_queue<frac, vector<frac>>pq;
        FOR(i, 0, N) {
            int L; cin >> L;
            pq.emplace(frac{ L,1 });
        }
        vector<double>res(5e5 + 5);
        FOR(k, 1, 5e5 + 1) {
            frac a = pq.top(); pq.pop();
            res[k] = 1.*a.x / a.c;
            pq.emplace(frac{ a.x,a.c + 1 });
        }
    
        LL Q; cin >> Q;
        FOR(i, 0, Q) {
            int k; cin >> k;
            double ans = res[k];
            cout << fixed << setprecision(10) << ans << "\n";
        }
    
        return 0;
    }