Problem

10/11

Sabbia

Problem

Modifica il programma in modo che risolva il seguente problema.

Durante una rapina in un negozio, un ladro ha trovato N scatole di polvere d'oro. Nella casella numerata i, la sabbia ha un valore di vi e un peso di wi>. Per portare via il bottino, il ladro usa uno zaino. È necessario determinare il massimo costo totale di sabbia che un rapinatore può trasportare se la capacità di carico dello zaino è limitata da W.
 
Puoi versare qualsiasi quantità di sabbia dalle scatole. Quindi il rapporto tra il costo della sabbia versata e il costo dell'intera scatola sarà uguale al rapporto tra il volume della sabbia versata e il volume dell'intera scatola.
 
Input
La prima riga del file di input contiene due numeri  - N e W (1 <= N <= 1000, 0 <= W <= 1000000). Questo è seguito da N righe di due interi ciascuna. La riga i-esima contiene il costo vi e il peso wi di sabbia nel iesimo cassetto. Tutti i numeri sono non negativi e non superano 106.
 
Uscita
Stampa il costo massimo desiderato con un errore non superiore a 0,0001.

 
Esempi
# Input Uscita
1
3 50
60 20
100 50
120 30
 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!