题解
【入门】淘淘捡西瓜
1 条题解
-
0
#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