解题思路
核心思路:把 N 层切成恰好 K 段连续非空区间,最小化各段和的最大值。答案有单调性:若峰值上限 x 可行,则所有 y>x 也可行,因此对答案二分。判定时从左到右贪心装箱:当前段再放下一项就会超过 x 就新开一段,最后看需要的段数是否不超过 K。因为 N≥K,段数偏少时可以继续切开,最大负载不会变差,所以「至多 K 段」与「恰好 K 段」等价。下界取 maxf[i],上界取总和。
实现方法:读入后先算 lo=maxf[i]、hi=∑f[i]。二分中点 mid,扫描数组统计段数;单层超过 mid 直接判不可行。可行则缩小上界,否则抬下界。结束时 lo 即为最小可行峰值。
复杂度分析
每次判定 O(N),二分次数 O(log∑f[i])。时间复杂度 O(Nlog∑f[i]),空间复杂度 O(N)。在 N≤5000、f[i]≤1000 下足够。