蓝桥杯--算法提高 快乐司机_蓝桥杯算法提高实现快乐司机

# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
 
const int maxn = 10005;
struct bag{
    int gi;
    int pi;
    double per;
}a[maxn];
 
int cmp(bag a, bag b)
{
    return a.per > b.per;
}
int main()
{
    int w, n, i;
 
    cin >> n >> w;
    for(i = 0; i < n; ++i)
    {
        cin >> a[i].gi >> a[i].pi;
        a[i].per = 1.0 * a[i].pi / a[i].gi;
    }
 
    sort(a, a + n, cmp);
    double maxValue = 0;
    int curSumWei = 0;
    for(i = 0; i < n && w - curSumWei >= a[i].gi; ++i)
    {
        maxValue += a[i].pi;
        curSumWei += a[i].gi;
    }
    if(i < n){
        maxValue += 1.0 * (w - curSumWei) / a[i].gi * a[i].pi;
    }
    printf("%.1f\n", maxValue);
}