P2497. 最短木板长度

解题思路

本题其实暗含一些贪心思想，但想到思路后更多考察的是代码细节上的实现，因此将本题归类为模拟类型。

核心思路

很容易想到，我们肯定要优先填充最短的那一块木板。因此，我们不妨先对所有木板进行从小到大排序。

示例说明

对于例子：

我们对所有木板排序得到如下所示：

在填充最短木板（高度为 3）的时候，我们先将它填充到跟第二短的木板（高度为 5）一样的高度。会得到以下结果：

填充完毕后，我们发现剩余木板长度还剩下 5，还可以继续进行填充。这个时候我们会继续考虑当前两个最短长度的木板（高度为 5）的填充，将它们填充到第三短的木板（高度为 7）的高度。会得到以下结果：

此时剩余木板长度为 1，但是此时我们存在 3 个长度为 7 的最短木板，无法再使得这三个最短木板的高度同时增加，因此正确答案为 7。

一般化抽象

如果我们所有的木板都遵循类似的贪心策略，每次补齐都只把木板补齐到下一个更长木板的高度。

当我们从小到大地考虑第 i 块木板的时候（它的高度是 heights[i]），此时必然存在已经有 i 块前面的木板都已经补齐到高度 heights[i] 了，包括这块木板自身，一共有 i+1 块木板的高度为 heights[i]。而下一个更长木板的高度为 heights[i+1]，如果想要把这 i+1 块木板的高度都补齐到 heights[i+1] 的话，一定需要 (heights[i+1] - heights[i]) * (i+1) 的木板材料。

假设此时剩余木板材料的高度为 rest。若：

• rest > (heights[i+1] - heights[i]) * (i+1)，则所有高度为 heights[i] 的木板都可以补到 heights[i+1] 的高度，我们还需要继续往下循环。
• rest <= (heights[i+1] - heights[i]) * (i+1)，则所有高度为 heights[i] 的木板无法补齐到 `heights[i+1]` 的高度。由于存在 (i+1) 块等高的木板，它们需要尽量地补到同一高度，它们最多每块只能增加 rest // (i+1) 的高度，而最终的总高度为 `heights[i] + rest // (i+1)`。

代码实现

那么我们的代码可以这样完成：

其中语句 heights.append(2 * 10**6) 是给 heights 数组末尾填充一个极大的数字，表示一个长度极大的木板。其作用是当我们处理 rest 极大，远超所有木板都补充到最长木板 max(heights) 所需要的消耗的情况。在那种情况下，我们会考虑此时一共 n 块高度为 max(heights) 的木板将如何补充到一个均匀的高度，也同样会执行 ans = heights[i] + rest // (i+1) 代码得到答案。

复杂度分析 设 n 为木板数量。

• 时间复杂度：O(n log n)。算法分两步：先对 heights 数组从小到大排序，这一步是 O(n log n)，也是全局瓶颈；随后往末尾追加一个哨兵极大值（O(1)），再从小到大遍历每块木板，每轮只做常数次加减乘除和一次比较——要么从 rest 中扣掉把前 i+1 块木板补齐到下一高度的消耗，要么算出答案 heights[i] + rest // (i+1) 后退出。遍历部分是 O(n)，合计 O(n log n)。
• 空间复杂度：O(1)（不计输入数组本身）。排序在原数组上就地完成，额外只用了 rest、ans、i 和一个哨兵元素，均为常数级开销。