【题解】小蓝的零食规划 —— 最小化每日热量最大值
一、题目解读
小蓝有 n 包零食，要在 m 天内按顺序吃完，每天吃的零食是连续的若干包。要求找到一种吃法，使得「每天吃的热量总和」中最大的那个值尽可能小（最小化最大值）。
这是典型的「二分查找求解最小化最大值」问题，核心思路是通过二分法确定 “每日最大热量” 的可行范围，再验证该值是否满足 “m 天吃完” 的条件。
二、解题思路
1. 确定二分边界
- 左边界（left）：单日至少要吃 1 包零食，因此左边界是所有零食中热量最高的那包（如果左边界比这个值小，那包热量最高的零食一天吃不完，不符合要求）。
- 右边界（right）：极端情况 ——1 天吃完所有零食，因此右边界是所有零食的热量总和。
2. 可行性验证（核心）
定义函数 check(m, p, x)，判断 “每日最大热量不超过 x” 时，能否在 m 天内吃完所有零食：
- 初始化天数
day=1，当日已吃热量sum=0； - 遍历每包零食：如果当前零食加入后不超过 x，就累加；否则新增一天，重新开始计算当日热量；
- 最终判断总天数是否≤m，若是则 x 是可行解。
3. 二分查找迭代
- 若当前中间值
mid可行，说明可以尝试更小的 “每日最大热量”，调整右边界； - 若不可行，说明需要增大 “每日最大热量”，调整左边界；
- 最终找到的最小可行值就是答案。
三、完整代码（适配题目输入输出）
package yjq260128;
import java.util.Scanner;
/**
* @author YJQ
* @date 2026/2/3 18:50
* @description 小蓝吃零食：最小化每日热量最大值
*/
public class main6 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 1. 读取输入：n包零食，m天
int n = scanner.nextInt();
int m = scanner.nextInt();
// 2. 读取每包零食的热量，同时初始化二分边界
long[] p = new long[n]; // 用long避免热量总和溢出
long left = 0; // 左边界：最大单包热量
long right = 0; // 右边界：所有零食热量总和
for (int i = 0; i < n; i++) {
p[i] = scanner.nextLong();
right += p[i]; // 累加得到总热量
if (p[i] > left) {
left = p[i]; // 更新为最大单包热量
}
}
long result = 0; // 存储最终答案
// 3. 二分查找核心逻辑
while (left <= right) {
long mid = (left + right) / 2; // 当前尝试的“每日最大热量”
if (check(m, p, mid)) { // 验证mid是否可行
result = mid; // 记录可行解
right = mid - 1; // 尝试更小的最大值
} else {
left = mid + 1; // 最大值太小，需要增大
}
}
// 4. 输出结果
System.out.println(result);
scanner.close();
}
/**
* 验证：每日最大热量为x时，能否在m天内吃完所有零食
* @param m 最多允许的天数
* @param p 零食热量数组
* @param x 每日最大热量限制
* @return 是否可行
*/
public static boolean check(int m, long[] p, long x) {
int day = 1; // 初始天数为1
long currentSum = 0; // 当天已吃的热量总和
for (long calory : p) {
if (currentSum + calory <= x) {
// 当天还能吃，累加热量
currentSum += calory;
} else {
// 当天吃不下了，新增一天
day++;
currentSum = calory; // 新的一天从当前零食开始吃
}
}
// 总天数≤m则可行
return day <= m;
}
}
四、代码关键说明
- 数据类型选择：使用
long而非int，避免零食包数多、单包热量高时，总和超出 int 的取值范围导致溢出。 - 输入处理：严格匹配题目输入格式 —— 第一行 n 和 m，第二行 n 个整数表示每包热量。
- check 函数：线性遍历数组，时间复杂度 O (n)，是验证可行性的核心，逻辑简单且高效。
- 二分效率：二分查找的迭代次数为 O (log (总热量 - 最大单包热量))，整体时间复杂度 O (n log S)（S 为总热量），远优于暴力枚举所有可能的方案。
五、测试案例演示
案例 1
输入：
plaintext
5 2
7 2 5 10 8
- 初始 left=10（最大单包热量），right=32（总热量 7+2+5+10+8=32）；
- 第一次 mid=21，check 验证：分 2 天（[7,2,5] 和 [10,8]），总天数≤2，可行，记录 result=21，调整 right=20；
- 后续迭代逐步缩小范围，最终找到最小可行值 18。
输出：18
案例 2
输入：
plaintext
3 3
1 2 3
- 初始 left=3，right=6；
- mid=4 时，check 验证：分 3 天（[1]、[2]、[3]），可行，记录 result=4，调整 right=3；
- mid=3 时，check 验证：分 3 天，可行，记录 result=3，调整 right=2，循环结束。
输出：3
六、总结
本题的核心是将 “最小化最大值” 问题转化为二分查找问题：
- 明确二分的 “值域”（不是数组下标）：左边界是最大单值，右边界是总和；
- 实现可行性验证函数，判断当前值是否满足条件；
- 通过二分迭代缩小范围，找到最优解。
这种思路不仅适用于 “吃零食” 问题，还能解决 “分割数组的最大值”“运输货物” 等同类问题，掌握后可快速应对这类经典算法题。
