Сортировка с компаратором




Task
Во время ограбления магазина вор обнаружил N ящичков с золотым песком. В ящичек под номером i песок имеет стоимость vi и вес wi. Чтобы унести награбленное, вор использует рюкзак. Требуется определить наибольшую суммарную стоимость песка, который может унести грабитель, если грузоподъемность рюкзака ограничена величиной W.
 
Из ящичков можно пересыпать любое количество песка, тогда отношение стоимости отсыпанного песка к стоимости всего ящичка будет равна отношению объема пересыпанного песка к объему всего ящичка.
 
Входные данные
первой строке входного файла записаны два числа  — N и W (1 <= N <= 1000, 0 <= W <= 1000000). Далее следует N строк по два целых числа в каждой. В i-ой строке записана стоимость vi и вес wi песка в i-ом ящичке. Все числа неотрицательные и не превосходят 106.
 
Выходные данные
Выведите искомую максимальную стоимость с погрешностью не более 0,0001.

Ввод Вывод
3 50
60 20
100 50
120 30
180.0000
(с) Григорьев Е., 2018
C++
Write a 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);
}  
Your last submission is saved in the editor window.
     

Results:

All results: