手伝いとお小遣い

2 secs 1024 MB

shinnshinn

問題

提出

テストケース

解説

この問題では、目標とする比率 $x$ を定め、その比率を実現できるかどうかを判定する方法を取ります。この判定作業を効率よく行うために二分探索を用います。

まず、比率を $x$ 以上にできるかを考えてみましょう。数式で示すと以下のようになります。

\frac{\sum P_i}{\sum E_i} \geqq x

これを式変形していきます。平均最大化の考え方に近いと思います。

\begin{aligned} \frac{\sum P_i}{\sum E_i} &\geqq x \\ \sum P_i &\geqq x \sum E_i \\ \sum P_i - x \sum E_i &\geqq 0 \\ \sum (P_i - xE_i) &\geqq 0 \\ \end{aligned}

このように変形出来ます。よって、 $k$ 個選んだ時、 $(P_i - xE_i)$ の総和が0以上になっていれば比率は $x$ 以上に出来ると判定できます。

証明は省略しますが、 $(P_i - xE_i)$ は大きい順に選ぶのが最適です。

計算量については、二分探索で $\log N$ 、判定でソートの部分が $N\log N$ かかります。よって全体で $O(N (\log N)^2)$ となります。

実装

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
int main() {
    int n, k;
    cin >> n >> k;
    vector<double> e(n), p(n);
    for(int i = 0;i < n; ++i){
        cin >> e[i];
    }
    for(int i = 0;i < n; ++i){
        cin >> p[i];
    }
​
    double ok = 0, ng = 1e18;
    for(int ii = 0;ii < 100; ++ii){
        double mid = (ok + ng)/2;
​
        vector<double> a(n);
        for(int i = 0;i < n; ++i){
            a[i] = p[i] - mid*e[i];
        }
​
        sort(a.rbegin(), a.rend());
        double sum = 0;
        for(int i = 0;i < k; ++i){
            sum += a[i];
        }
​
        if(sum >= 0){
            ok = mid;
        }else{
            ng = mid;
        }
    }
​
    printf("%.10f\n", ok);
    return 0;
}