Problem

10/11

Cát

Problem

Sửa đổi chương trình để chương trình giải quyết vấn đề sau.

Trong khi cướp một cửa hàng, một tên trộm đã tìm thấy N hộp bụi vàng. Trong ô được đánh số i, cát có giá trị vi và trọng lượng là wi. Để mang đi chiến lợi phẩm, tên trộm sử dụng ba lô. Cần phải xác định tổng chi phí cát lớn nhất mà một tên cướp có thể mang theo nếu sức chứa của ba lô bị giới hạn bởi W.
 
Bạn có thể đổ bất kỳ lượng cát nào từ các hộp. Sau đó, tỷ lệ giữa chi phí cát đổ với chi phí của toàn bộ hộp sẽ bằng tỷ lệ giữa thể tích cát đổ với thể tích của toàn bộ hộp.
 
Đầu vào
Dòng đầu tiên của tệp đầu vào chứa hai số  - N và W (1 <= N <= 1000, 0 <= W <= 1000000). Tiếp theo là các dòng N mỗi dòng có hai số nguyên. Dòng thứ i chứa chi phí vi và trọng số wi cát trong ngăn kéo thứ i. Tất cả các số đều không âm và không vượt quá 106.
 
Đầu ra
In chi phí tối đa mong muốn với sai số không quá 0,0001.

 
Ví dụ
<đầu>

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++
# Đầu vào Đầu ra
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!