洛谷P3817题解：基于贪心算法的糖果分配优化策略
1天前
一、题目解读
洛谷P3817题目要求处理n个盒子中的糖果分配问题：给定每个盒子的糖果数a[i]及限制值x，需通过吃掉部分糖果，确保任意相邻盒子(a[i-1] + a[i])的总和不超过x。输出最小需吃掉的糖果总数。题目关键在于高效处理相邻关系，避免全局遍历，降低时间复杂度。
二、解题思路
本题采用贪心策略的核心逻辑：局部最优解可推导全局最优。由于需最小化总消耗，每次处理相邻盒子时，优先减少当前盒子（即a[i]）的糖果数，因其能直接影响下一对相邻盒子的判断。若当前减少量不足，再补充减少前一个盒子（即a[i-1]）的糖果。该策略确保每一步的“损耗”对后续影响最大化，从而避免回溯或复杂计算。
三、解题步骤
1. 输入与初始化：读取n、x及盒子数组a[]，初始化总消耗total_eaten=0。
2. 遍历处理：从左到右遍历相邻盒子对(i-1,i)，若a[i-1] + a[i] > x，则需调整：
○ 计算需减少的总量：need_to_eat = (a[i-1] + a[i]) - x。
○ 优先从a[i]中减少，取min(need_to_eat, a[i])以避免过量。
○ 若仍需调整，从a[i-1]中补充减少量，更新total_eaten。
3. 输出结果：最终total_eaten即为最小消耗。
四、代码与注释
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, x;
cin >> n >> x; // 输入盒子数量n和限制值x
vector<int> a(n); // 存储每个盒子的糖果数
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
long long total_eaten = 0; // 记录总消耗（需long long防溢出）
// 从左到右处理相邻盒子
for (int i = 1; i < n; ++i) {
if (a[i-1] + a[i] > x) { // 若相邻和超限
int need_to_eat = a[i-1] + a[i] - x; // 计算需减少的总量
int can_eat = min(need_to_eat, a[i]); // 优先从当前盒子减少
a[i] -= can_eat; // 更新当前盒子糖果数
if (can_eat < need_to_eat) { // 若仍需调整
a[i-1] -= (need_to_eat - can_eat); // 从前一个盒子补充减少
}
total_eaten += need_to_eat; // 累加总消耗
}
}
cout << total_eaten << endl; // 输出结果
return 0;
}五、总结
该解法通过贪心算法实现线性时间复杂度O(n)，核心在于“优先当前盒子减少”的策略，确保局部决策的最优性。代码简洁且易于理解，无需复杂数据结构或动态规划。注意变量类型需使用long long避免大数溢出。此思路适用于类似“相邻约束优化”的问题，为算法竞赛中常见的解题模式。
原创内容 转载请注明出处
