GPT答: |
7i24.cn
|
【解题思路】
首先,我们需要将糖果按照箱子的容量进行分组。对于每一组,我们需要找出其中最大的一捆糖果,并求其数量之和。
为了尽可能使得每个箱子中最大一捆糖果的数量较小,我们可以采用贪心策略。具体地,我们从第一捆开始遍历所有的糖果,并将它们依次放入当前箱子中。如果当前箱子已经装满了(即当前箱子中的糖果数量等于M),则记录下该箱子中最大一捆糖果的数量,并继续放入下一个新的空箱子。
【算法步骤】
1. 读取输入数据N和M;
2. 读取N个整数表示每捆糖果的数量;
3. 初始化变量sum为0,表示所有箱子中最大一捆糖果数量之和;
4. 初始化变量max_candy为0,表示当前正在处理的这个空箱子里面最多能装多少个;
5. 遍历N个整数:
- 如果max_candy加上当前这束还不超过M,则更新max_candy为它们两者之间较大值;
- 否则将max_candy加到sum上,并重置max_candy为当前这束。
6. 将剩余未处理完毕但是不足以填满一个新盒时的max_candy加到sum上;
7. 输出sum。
【代码实现】
```cpp
#include <iostream>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
int sum = 0; // 所有箱子中最大一捆糖果数量之和的最小值
int max_candy = 0; // 当前正在处理的这个空箱子里面最多能装多少个
for (int i = 0; i < N; i++) {
int candy;
cin >> candy;
if (max_candy + candy <= M) { // 如果当前这束糖果还可以放入当前箱子中
max_candy = max(max_candy, candy); // 更新当前这个空箱子里面最多能装多少个糖果
} else { // 当前这束糖果不能放入当前箱子中,需要换一个新的空箱子来装
sum += max_candy; // 将之前处理过程中得到的每一个满盒(即max_candy)都加到sum上,并重置max_candy为当前这束
if (candy > M) {
sum += -1;
break;
}
max_candy = candy;
}
if (i == N - 1) {
sum += max_candy;
}
}
cout << sum << endl;
return 0;
}
```
|