Problem

10/11

Sable

Problem

Modifiez le programme afin qu'il résolve le problème suivant.

En dévalisant un magasin, un voleur a trouvé N boîtes de poudre d'or. Dans la case numérotée i, le sable a une valeur de vi et un poids de wi. Pour emporter le butin, le voleur utilise un sac à dos. Il est nécessaire de déterminer le plus grand coût total de sable qu'un voleur peut transporter si la capacité de charge du sac à dos est limitée par W.
 
Vous pouvez verser n'importe quelle quantité de sable des boîtes. Ensuite, le rapport du coût du sable versé au coût de la boîte entière sera égal au rapport du volume de sable versé au volume de la boîte entière.
 
Entrée
La première ligne du fichier d'entrée contient deux nombres  - N et W (1 <= N <= 1000, 0 <= W <= 1000000). Ceci est suivi de lignes N de deux entiers chacune. La i-ième ligne contient le coût vi et le poids wi de sable dans le iième tiroir. Tous les nombres sont non négatifs et ne dépassent pas 106.
 
Sortie
Imprimez le coût maximum souhaité avec une erreur ne dépassant pas 0,0001.

 
Exemples
3 50
60 20
100 50
120 30
# Entrée Sortie
1 180.0000

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++
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!