返回题解分享
讨论 / 题解分享/ 帖子详情

阿里巴巴与金币 - 题解

70%,不知道哪里错了,有佬能帮看看嘛

#include <bits/stdc++.h>
using namespace std;

struct Gold
{
    int m;
    int v;
    double aver;
    bool operator<(const Gold& other) const
    {
        return aver < other.aver;
    }
};

int main()
{
    int N, T;
    int m, v;
    cin >> N >> T;
    double sum = 0;
    priority_queue<Gold> q;

    for(int i = 0; i < N; i++)
    {
        cin >> m >> v;
        q.push({m, v, (double)v/m});
    }

    while(T > 0)
    {
        Gold g = q.top();
        q.pop();
        // 背包能装下现在的所有金币
        if(T > g.m)
        {
            sum += g.v;
        }
        else
        {
            sum += T * g.aver;
        }
        T -= g.m;
    }

    printf("%.2lf", sum);
}
0 回复 0 转发 0 喜欢 5 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!