Problem

10/11

رمل

Problem

عدل البرنامج ليحل المشكلة التالية.

أثناء السطو على متجر ، عثر لص على صناديق N من غبار الذهب. في المربع المرقّم i ، يكون للرمل قيمة v i ووزن w i . لحمل المسروقات بعيدًا ، يستخدم اللص حقيبة ظهر. يلزم تحديد أكبر تكلفة إجمالية للرمال التي يمكن أن يحملها السارق إذا كانت سعة حقيبة الظهر محدودة بـ W .
& nbsp؛
يمكنك صب أي كمية من الرمل من الصناديق. ثم تكون نسبة تكلفة الرمل المصبوب إلى تكلفة الصندوق بأكمله مساوية لنسبة حجم الرمل المصبوب إلى حجم الصندوق بأكمله.
& nbsp؛
إدخال
يحتوي السطر الأول من ملف الإدخال على رقمين & nbsp؛ - & nbsp؛ N و W (1 & lt؛ = N & lt؛ = 1000، 0 & lt؛ = W & lt؛ = 1000000). ويتبع ذلك سطور N من عددين صحيحين لكل منهما. يحتوي السطر رقم i -th على التكلفة v i والوزن w i من الرمل في الدرج i الخامس. جميع الأرقام غير سالبة ولا تتجاوز 10 6 .
& nbsp؛
الإخراج
اطبع التكلفة القصوى المطلوبة بخطأ لا يزيد عن 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!