1 条题解

  • 0
    @ 2026-2-1 16:08:56
    #include<bits/stdc++.h>
    using namespace std;
    
    // 存储每堆金币的信息:m-重量,v-价值
    struct node{
        int m,v;
    }arr[110]; 
    
    // 比较函数:按单位价值(价值/重量)从高到低排序
    // 贪心策略:优先拿单位价值高的金币,保证总价值最大
    bool cmp(node a,node b){
        return a.v*1.0/a.m > b.v*1.0/b.m;
    }
    
    int main(){
        int n,t;
        cin >> n >> t; // [1] 输入金币堆数n和背包容量t
        
        // [2] 输入每堆金币的重量和价值
        for(int i = 0; i < n; i++)
            cin >> arr[i].m >> arr[i].v;
        
        sort(arr, arr + n, cmp); // [3] 按单位价值降序排序金币堆
        
        double sum = 0; // 记录可带走的最大总价值
        // [4] 贪心选取金币:优先拿单位价值高的
        for(int i = 0; i < n && t > 0; i++){
            if(t >= arr[i].m){
                // 背包容量足够,整堆拿走
                sum += arr[i].v;
                t -= arr[i].m;
            }else{
                // 背包容量不足,拿走当前堆的一部分
                sum += t * (arr[i].v*1.0/arr[i].m);
                t = 0;
            }
        }
        
        cout << setprecision(2) << fixed << sum; // [5] 输出保留两位小数的总价值
        return 0;	
    }
    
    • 1

    信息

    ID
    1035
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    2
    已通过
    1
    上传者