Problem

10/11

Arena

Problem

Modifique el programa para que resuelva el siguiente problema.

Mientras robaba en una tienda, un ladrón encontró N cajas de polvo de oro. En la casilla numerada i, la arena tiene un valor de vi y un peso de wi. Para llevarse el botín, el ladrón usa una mochila. Se requiere determinar el mayor costo total de arena que un ladrón puede llevar si la capacidad de carga de la mochila está limitada por W.
 
Puedes verter cualquier cantidad de arena de las cajas. Entonces, la relación entre el costo de la arena vertida y el costo de toda la caja será igual a la relación entre el volumen de arena vertida y el volumen de toda la caja.
 
Entrada
La primera línea del archivo de entrada contiene dos números  - N y W (1 <= N <= 1000, 0 <= W <= 1000000). A esto le siguen líneas N de dos enteros cada una. La línea i-ésima contiene el costo vi y el peso wi de arena en el cajón ith. Todos los números son no negativos y no exceden 106.
 
Salida
Imprima el costo máximo deseado con un error de no más de 0.0001.

 
Ejemplos

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++
# Entrada Salida
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!