6 条题解

  • 1
    @ 2024-12-28 20:08:53
    // https://dashoj.com/p/77
    
    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    
    struct g {
        ll m; // 重量
        ll u; // 价值
        double x; // 每一重的价值
    };
    
    ll n, t;
    vector<g> gs;
    
    int main() {
        cin >> n >> t;
        for (int i = 0; i < n; i++) {
            ll m, u;
            cin >> m >> u;
            gs.push_back({m, u});
            gs[i].x = (double) u / (double) m;
        }
        sort(gs.begin(), gs.end(), [](g a, g b) {
            return a.x > b.x; // 按价值 / 重量从大到小排序
        });
        double ans = 0; // 答案
        for (int i = 0; i < n; ++i) {
            if (t >= gs[i].m) {
                t -= gs[i].m;
                ans += gs[i].u;
            } else {
                ans += t * gs[i].x;
                break;
            }
        }
        printf("%.2lf", ans);
        return 0;
    }
    
    

    信息

    ID
    77
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    396
    已通过
    90
    上传者