Problem

10/11

Areia

Problem

Modifique o programa para que resolva o seguinte problema.

Ao roubar uma loja, um ladrão encontrou N caixas de ouro em pó. Na caixa numerada i, a areia tem um valor de vi e um peso de wi. Para levar o saque, o ladrão usa uma mochila. É necessário determinar o maior custo total de areia que um ladrão pode carregar se a capacidade de carga da mochila for limitada por W.
 
Você pode derramar qualquer quantidade de areia das caixas. Então, a razão entre o custo da areia derramada e o custo da caixa inteira será igual à razão entre o volume da areia derramada e o volume da caixa inteira.
 
Entrada
A primeira linha do arquivo de entrada contém dois números  - N e W (1 <= N <= 1000, 0 <= W <= 1000000). Isso é seguido por N linhas de dois inteiros cada. A linha i contém o custo vi e o peso wi de areia na ia gaveta. Todos os números são não negativos e não excedem 106.
 
Saída
Imprima o custo máximo desejado com um erro não superior a 0,0001.

 
Exemplos
# Entrada Saída
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!