Dropping tests POJ2976

投稿日：2022/09/12 更新日:2022/09/12

問題

$n$ 個のテストがあり、 $b_i$ 満点中 $a_i$ 点獲得しました。平均は以下の式で計算されます。

100\cdot\frac{\sum_{i=1}^{n} a_i}{\sum_{i=1}^{n}b_i}

また、整数 $k$ が与えられます。受けたテストのうち $k$ 個取り除きます。その後、平均の最大値を小数点以下は四捨五入して整数で出力してください。

解法

平均を $v$ 以上にできるかで二分探索をします。

式を変形していきます。

\begin{aligned} 100\cdot\frac{\sum_{i=1}^{n} a_i}{\sum_{i=1}^{n}b_i} &\geqq v \\ 100\sum_{i=1}^{n} a_i &\geqq v\sum_{i=1}^{n}b_i \\ \sum_{i=1}^{n}100a_i-vb_i &\geqq 0 \end{aligned}

$100a_i-vb_i$ の値が大きい方から $n-k$ 個選び、その総和が0以上であれば良いことが分かります。

実装

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve(int n, int k){
    vector<long long> a(n), b(n);
    for(int i = 0;i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0;i < n; ++i){
        cin >> b[i];
    }

    double ng = 1e18, ok = 0;
    for(int i = 0;i < 100; ++i){
        double mid = (ok + ng)/2;

        vector<double> s(n);
        for(int i = 0;i < n; ++i){
            s[i] = 100*a[i] - mid*b[i];
        }
        sort(s.begin(), s.end());
        double sum = 0;
        for(int i = n-1;i >= k; --i){
            sum += s[i];
        }

        if(sum >= 0){
            ok = mid;
        }else{
            ng = mid;
        }
    }

    printf("%.0f\n", ok);
}

int main(){
    int n, k;
    cin >> n >> k;
    while(!(n == 0 && k == 0)){
        solve(n, k);
        cin >> n >> k;
    }

    return 0;
}