Module: コンパレータによるソート


Problem

10/11

砂

Problem

プログラムを修正して、次の問題を解決してください。

店に強盗に入ったとき、泥棒が N 箱の砂金を発見しました。 i という番号のボックスでは、砂の値は vi 、重量は wi。略奪品を持ち去るために、泥棒はバックパックを使用します。バックパックの積載量が W によって制限されている場合、強盗が運ぶことができる砂の最大の合計コストを決定する必要があります。
 
ボックスから任意の量の砂を注ぐことができます。この場合、箱全体のコストに対する注がれた砂のコストの比率は、箱全体の体積に対する注がれた砂の体積の比率に等しくなります。
 
入力
入力ファイルの最初の行には 2 つの数値が含まれています  -N および W (1 <= N <= 1000、0 <= W <= 1000000)。これに、それぞれ 2 つの整数からなる N 行が続きます。 i 行目には、コスト vi と重み wi が含まれています。 i 番目の引き出しに砂が入っています。すべての数値は負ではなく、106 を超えません。
 
出力
希望の最大コストを誤差 0.0001 以内で出力します。

 
例
<頭> <本体>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# 入力 出力
1
3 50
60 20
100 50
120 30
 180.0000
Write the program below 
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;

struct sand {
    int cost, weight;
    double cw;

    sand() { }
    
    sand(int _cost, int _weight) {
        this->cost = _cost;
        this->weight = _weight;
        this->cw = 1. * _cost / _weight;
    }
};

bool cmp(sand a, sand b) {    
}

vector<sand>sandArray(0);
int n;
int w;
double answer;

int main() {
    cin >> n >> w;
    sandArray.resize(n);
    for (int i = 0; i < n; i++) {
        int cost, weight;
        cin >> cost >> weight;
        sandArray.at(i) = sand(cost, weight);
    }

    sort(sandArray.begin(), sandArray.end(), cmp);

    for (int i = 0; i < n; i++)
        if (sandArray.at(i).weight <= w) {
            w -= sandArray.at(i).weight;
            answer += sandArray.at(i).cost;
        }
        else {
            answer += sandArray.at(i).cw * w;
            w = 0;
        }
        
    printf("%.4lf", answer);
}

     

Program check result

To check the solution of the problem, you need to register or log in!