top1编程
← 返回题目
题解

【入门】淘淘捡西瓜

1 条题解

  • 0
    @ 2026-7-28 23:24:03
    #include<bits/stdc++.h>
    using namespace std;
    int a[105];
    int main(){
        int n, x, sum = 0, s = 0; // n:西瓜数量, x:背包容量, sum:备选变量未使用, s:当前已装西瓜总重量
        cin >> n >> x; // 输入西瓜数量和背包容量
        // 读取每个西瓜的重量
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        sort(a+1, a+n+1); // 对西瓜按重量升序排序(贪心策略:优先选轻的)
        int y = 0; // y:记录最多能装的西瓜数量
        // 从小到大尝试装入西瓜,直到装不下为止
        for(int i = 1; i <= n; i++){
            s += a[i]; // 累加当前西瓜重量
            if(s <= x){ // 如果装入当前西瓜后总重量不超过背包容量
                y++; // 成功装入,西瓜数量加1
            } else {
                break; // 装不下当前西瓜,退出循环(后续更重的西瓜也装不下)
            }
        }
        cout << y; // 输出最多能装的西瓜数量
        return 0;
    }
    
    • 1