Codeforces 2108F

Codeforces 2108F | AI生成和翻译

Home 2025.05

让我们深入探讨为什么提供的Java代码能够解决”倒塌的塔楼”问题。该问题涉及一个包含 \( n \) 座塔楼的数组，每座塔楼高度为 \( a_i \geq 0 \)。你可以推倒位置 \( i \) 的塔楼，这会使后续 \( a_i \) 座塔楼的高度增加1（如果剩余塔楼不足则影响更少塔楼），然后将 \( a_i \) 设为0。目标是以任意顺序恰好推倒所有 \( n \) 座塔楼各一次，并确保最终数组是非递减的（即对于任意 \( i < j \)，位置 \( i \) 的高度不超过位置 \( j \) 的高度）。输出结果是最终数组的最大MEX值，其中MEX是指数组中不存在的最小非负整数。

问题分析

操作定义：
- 推倒高度为 \( a_i \) 的塔楼 \( i \)：
  - 将位置 \( i+1, i+2, \dots, i+a_i \) 的塔楼高度增加1（如果这些位置存在塔楼）
  - 将 \( a_i \) 设为0
- 每座塔楼必须恰好被推倒一次，顺序任意
- 如果 \( a_i = 0 \)，推倒塔楼 \( i \) 不会影响其他塔楼
非递减最终数组：
- 所有操作完成后，最终数组 \( b_1, b_2, \dots, b_n \) 必须满足对所有 \( i < n \) 有 \( b_i \leq b_{i+1 \)
MEX：
- 最终数组的MEX是不存在于 \( {b_1, b_2, \dots, b_n} \) 中的最小非负整数 \( m \)
- 由于数组是非递减的，如果数组包含值 \( 0, 1, 2, \dots, k-1 \)（可能有重复）但不包含 \( k \)，则MEX为 \( k \)
- 目标是最大化这个MEX值
MEX的解释：
- 要使MEX为 \( m \)，最终数组必须至少包含从0到 \( m-1 \) 的所有整数各一次，且不能出现 \( m \)
- 由于数组是非递减的，实现MEX为 \( m \) 意味着最终数组的值形如 \( 0, 0, \dots, 1, 1, \dots, m-1, m-1 \)，其中从0到 \( m-1 \) 的每个整数至少出现一次，且没有值 \( m \) 或更高
关键洞察：
- MEX \( m \) 对应于最终数组中至少有一个位置包含从0到 \( m-1 \) 的每个值
- 等价地，对于MEX为 \( m \)，我们需要最终数组中至少有 \( m \) 个位置，使得位置 \( i \) 的值至少为 \( i - (n - m) \)，因为：
  - 最后 \( m \) 个位置（从索引 \( n-m+1 \) 到 \( n \)）必须覆盖值0到 \( m-1 \)
  - 位置 \( n-m+1 \) 的值应至少为0，位置 \( n-m+2 \) 至少为1，……，位置 \( n \) 至少为 \( m-1 \)
- 这转化为要求位置 \( i \) 的最终高度至少为 \( \max(0, m - (n - i + 1)) = \max(0, m - n + i) \)

解决方案方法

代码使用二分查找来找到最大可能的MEX \( m \)。对于每个候选的 \( m \)，它检查是否可能实现一个非递减的最终数组，其中每个位置 \( i \) 的高度至少为 \( \max(0, m - n + i) \)。这确保了最后 \( m \) 个位置可以覆盖值0到 \( m-1 \)，使得MEX至少为 \( m \)。

二分查找

范围：MEX \( m \) 至少为0（空数组情况），最多为 \( n \)（因为我们需要至少 \( m \) 个位置来包含值0到 \( m-1 \)）。因此，在 \( [0, n] \) 范围内搜索 \( m \)
检查函数：对于给定的 \( m \)，确定是否存在一种推倒塔楼的顺序，使得最终数组满足：
- 对所有 \( i \) 有 \( b_i \geq \max(0, m - n + i) \)
- 数组是非递减的

检查函数

检查函数使用差分数组方法模拟是否可以通过某种操作顺序达到所需高度。

所需高度：
- 对于MEX \( m \)，位置 \( i \) 需要最终高度 \( b_i \geq \text{need}_i \)，其中： \[ \text{need}_i = \max(0, m - n + i) \]
- 这确保了位置 \( n-m+1 \) 到 \( n \) 的高度分别至少为0, 1, …, \( m-1 \)
差分数组：
- 代码使用差分数组 \( d \) 来跟踪操作的累积效果
- 初始化所有 \( d[i] = 0 \)
- 对于每个位置 \( i \)：
  - 计算累积和：\( d[i] += d[i-1] \)（如果 \( i > 0 \)），表示位置 \( i \) 当前的额外块数
  - 检查是否 \( d[i] \geq \text{need}_i \)。如果不是，则无法达到所需高度，返回 \( false \)
  - 计算推倒塔楼 \( i \) 时影响的右侧范围长度： \[ \text{len} = d[i] - \text{need}_i + a_i \]
    - \( d[i] - \text{need}_i \)：满足最低要求后可用的额外块数
    - \( a_i \)：塔楼 \( i \) 的高度贡献的块数
    - 这个 \( \text{len} \) 表示当推倒塔楼 \( i \) 时，可以增加其右侧多少个位置的高度
  - 更新差分数组：
    - 增加 \( d[i+1] \)（如果 \( i+1 < n \)）以开始推倒塔楼 \( i \) 的影响
    - 减少 \( d[i + \text{len} + 1] \)（如果 \( i + \text{len} + 1 < n \)）以在 \( \text{len} \) 个位置后结束影响
可行性：
- 差分数组模拟了基于当前状态推倒塔楼 \( i \) 并调整高度后的效果
- 如果循环完成而没有返回 \( false \)，则可以实现MEX \( m \) 所需的高度
为什么这种方法有效：
- 检查函数不模拟实际的操作顺序，而是验证是否存在满足高度要求的操作顺序
- 差分数组方法确保添加到每个位置的块数与某个有效操作序列一致
- 非递减条件被隐式满足，因为所需高度 \( \text{need}_i = \max(0, m - n + i) \) 是非递减的（随着 \( i \) 增加，\( m - n + i \) 增加或保持为0）

主循环

读取测试用例数量 \( t \)
对于每个测试用例：
- 读取 \( n \) 和数组 \( a \)
- 在0到 \( n \) 范围内对 \( m \) 执行二分查找
- 使用检查函数确定MEX \( m \) 是否可实现
- 更新 \( lo \)（如果可实现）或 \( hi \)（如果不可实现）
输出每个测试用例的最大 \( m \)（即 \( lo \)）

代码解决问题原因

二分查找的正确性：
- 二分查找找到使检查函数返回 \( true \) 的最大 \( m \)
- 由于MEX \( m \) 的可行性意味着所有更小MEX值（更低的 \( m \) 需要更少位置且高度要求更低）的可行性，二分查找能正确识别最大可能MEX
检查函数的准确性：
- 检查函数确保每个位置 \( i \) 在所有操作后能够拥有至少 \( \max(0, m - n + i) \) 个块
- 差分数组模拟推倒塔楼的累积效果，考虑每座塔楼贡献 \( a_i \) 个块给后续 \( a_i \) 个位置
- 通过从左到右处理位置并调整差分数组，验证初始高度 \( a_i \) 是否可以重新分配以满足所需高度
处理非递减约束：
- 所需高度 \( \max(0, m - n + i) \) 是非递减的，这与问题对最终数组非递减的要求一致
- 如果检查函数成功，通过确保每个位置达到或超过所需高度，可以使结果数组非递减
效率：
- 二分查找：\( O(\log n) \) 次迭代（因为 \( m \leq n \)）
- 检查函数：每次调用 \( O(n) \)，因为它处理每个位置一次并每次以常数时间更新差分数组
- 每个测试用例总计：\( O(n \log n) \)
- 所有测试用例总计：由于 \( \sum n \leq 10^5 \)，总体复杂度为 \( O(t \cdot n \log n) \)，在3秒时间限制内可行
边界情况：
- \( n = 1 \)：如果 \( a_1 = 0 \)，MEX = 1（数组变为[0]）。如果 \( a_1 > 0 \)，MEX = 0（数组变为[0]）。代码正确处理这种情况
- 大的 \( a_i \)：虽然 \( a_i \leq 10^9 \)，但只影响前 \( n-i \) 个位置，代码使用数组限制正确约束了影响范围
- 所有 \( a_i = 0 \)：最终数组全为零，MEX = 1。检查函数确认这一点
- 混合值：二分查找和检查函数处理任意的 \( a_i \geq 0 \)

Java代码细节

Java代码使用BufferedReader和PrintWriter进行高效I/O，按要求适配了C++逻辑。关键方面：

输入处理：
- 使用BufferedReader读取行，StringTokenizer解析整数
- 读取 \( t \)，然后对每个测试用例读取 \( n \) 和数组 \( a \)
Checker类：
- 封装检查逻辑以模拟C++的lambda函数
- 使用数组 \( d \) 模拟差分数组方法
输出：
- 使用PrintWriter输出每个测试用例的结果，使用out.flush()确保所有输出被写入
性能：
- Java代码保持每个测试用例相同的 \( O(n \log n) \) 复杂度
- BufferedReader和PrintWriter确保I/O对于 \( \sum n \leq 10^5 \) 足够快

结论

代码通过以下方式解决”倒塌的塔楼”问题：

使用二分查找找到最大MEX \( m \)
采用基于差分数组的检查函数验证初始塔楼高度是否可以重新分配以实现具有所需高度的非递减数组
通过所需高度的非递减特性和操作序列的可行性确保正确性
处理所有边界情况并满足时间和内存约束

Java实现忠实地转换了C++逻辑，使用高效I/O满足问题要求。

Back Donate