Problem

10/11

شن

Problem

برنامه را تغییر دهید تا مشکل زیر را حل کند.

دزد هنگام سرقت از یک فروشگاه، جعبه های N از گرد و غبار طلا را پیدا کرد. در کادر شماره i، شن مقدار vi و وزن wi. دزد برای بردن غارت از کوله پشتی استفاده می کند. در صورتی که ظرفیت حمل کوله پشتی توسط W محدود شده باشد، باید بیشترین هزینه کل ماسه ای که یک سارق می تواند حمل کند، تعیین شود.
 
می توانید هر مقدار ماسه را از جعبه ها بریزید. سپس نسبت هزینه ماسه ریخته شده به هزینه کل جعبه برابر با نسبت حجم ماسه ریخته شده به حجم کل جعبه خواهد بود.
 
ورودی
خط اول فایل ورودی شامل دو عدد است  - N و W (1 <= N <= 1000، 0 <= W <= 1000000). به دنبال آن خطوط N هر کدام از دو عدد صحیح دنبال می شود. خط i-امین شامل هزینه vi و وزن wi است. ماسه در کشوی iام. همه اعداد غیر منفی هستند و از 10 تجاوز نمی کنند6.
 
خروجی
حداکثر هزینه مورد نظر را با خطای حداکثر 0.0001 چاپ کنید.

 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
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!