Problem

10/11

Sand

Problem

Bearbeiten Sie das Programm so, dass es das nächste Problem löst.

Bei einem Ladenüberfall entdeckte der Dieb N Kisten mit goldenem Sand. In der Box mit der Nummer i hat der Sand einen Wert von vi und ein Gewicht von wi. Um das Gestohlene zu entführen, benutzt der Dieb einen Rucksack. Es ist erforderlich, den größten Gesamtwert des Sandes zu ermitteln, den ein Einbrecher tragen kann, wenn die Tragfähigkeit des Rucksacks auf W begrenzt ist.
 
Jede Menge Sand kann aus den Kisten gegossen werden. Dann ist das Verhältnis des Wertes des ausgetretenen Sandes zum Wert des gesamten Kastens gleich dem Verhältnis des Volumens des ausgetretenen Sandes zum Volumen des gesamten Kastens.
 
Eingabe
In der ersten Zeile der Eingabedatei sind zwei Zahlen geschrieben: N und W (1 <= N <= 1000, 0 <= W <= 1000000). Gefolgt von N Zeilen mit jeweils zwei Ganzzahlen. In der i-te Zeile sind die Kosten für vi und das Gewicht des wi Sandes in der i-te Box angegeben. Alle Zahlen sind nicht negativ und überschreiten 106 nicht.
 
Ausgabe
Geben Sie den gewünschten maximalen Wert mit einem Fehler von nicht mehr als 0,0001 aus.

 
Beispiele
№ Eingabe Ausgabe
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!