K Best POJ3111

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

問題

$N$ 個の宝石があります。 $i$ 番目の宝石の価値は $v_i$ 、重さは $w_i$ です。整数 $k$ が与えられます。この中から $k$ 個選んで単位重さあたりの価値の最大値を求めてください。なお、単位重さあたりの価値は以下の式で求まります。

\begin{aligned} \frac{\sum_{j = 1}^{k} v_i}{\sum_{j = 1}^{k} w_i} \end{aligned}

解法

単位重さあたりの価値を $x$ 以上にできるか、で二分探索します。

不等式を変形していきます。

\begin{aligned} \frac{\sum_{j = 1}^{k} v_i}{\sum_{j = 1}^{k} w_i} &\geqq x \\ \sum_{j = 1}^{k} v_i &\geqq x\sum_{j = 1}^{k} w_i \\ \sum_{j = 1}^{k} (v_i - xw_i) &\geqq 0 \end{aligned}

よって、 $v_i - xw_i$ の値が大きい物から $k$ 個選び、総和が0以上であるか判定すれば良いです。

実装

二分探索のループ回数が100回だとTLEしてしまいました。50回だと通りました。

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

struct Jewel{
    int v, w;
};

int main(){
    int n, k;
    cin >> n >> k;
    vector<Jewel> j(n);
    for(int i = 0;i < n; ++i){
        cin >> j[i].v >> j[i].w;
    }

    vector<double> jj(n);
    double ok = 0, ng = 1e8;
    for(int ii = 0;ii < 50; ++ii){
        double mid = (ok+ng)/2;

        for(int i = 0;i < n; ++i){
            jj[i] = j[i].v - mid*j[i].w;
        }
        sort(jj.begin(), jj.end());
        double sum = 0;
        for(int i = n-1;i >= n-k; --i){
            sum += jj[i];
        }

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

    vector<pair<double,int>> p(n);
    for(int i = 0;i < n; ++i){
        p[i].first  = j[i].v - ok*j[i].w;
        p[i].second = i+1;
    }
    sort(p.begin(), p.end());

    cout << p[n-1].second;
    for(int i = n-2;i  >= n-k; --i){
        cout << " " << p[i].second;
    }
    cout << endl;

}