C. Have Your Cake and Eat It Too 详细题解

题目重述

有一块蛋糕被切成 $n$ 块，每块对三个人（爱丽丝、鲍勃、查理）分别有估值 $a_i, b_i, c_i$。已知三个数组的总和相同，均为 $tot$。要求将整个蛋糕切成三个连续且不相交的子数组（每个子数组包含若干块），分配给三个人，使得每个人得到的子数组在其自己估值下的总和至少为 $\lceil tot/3 \rceil$。求任意一种分配方案，若不存在输出 $-1$。

核心思路

由于子数组必须连续且不重叠，问题等价于在 $1$ 到 $n$ 的排列中切出两个分界点，将序列分成三段（每段可能为空？但每人至少需要一块，且 $n \ge 3$，实际上每个人得到非空段）。我们只需要为每个人分配一个连续段，且三个段恰好覆盖整个 $[1,n]$ 且不重叠。

一种常见的技巧是枚举三人获得段的顺序。因为最终三段的排列顺序可以是任意的（例如 Alice 拿最左边一段，Bob 拿中间，Charlie 拿右边；或者 Alice 拿中间段等）。事实上，因为段必须连续且覆盖整个序列，所以三个段在数组中的顺序恰好是 $1 \dots n$ 的一种划分，每个段对应一个人。如果我们固定了三人对应的段顺序（即谁拿第一段、谁拿第二段、谁拿第三段），那么问题就变成了：能否找到两个分界点 $p$ 和 $q$（$1 \le p < q < n$），使得第一段 $[1,p]$ 在对应人的估值下和 $\ge need$，第二段 $[p+1,q]$ 在对应人的估值下和 $\ge need$，第三段 $[q+1,n]$ 在对应人的估值下和 $\ge need$，其中 $need = \lceil tot/3 \rceil$。

由于 $n$ 不超过 $2\times 10^5$，且 $t$ 的总 $n$ 和也不超过 $2\times 10^5$，枚举所有顺序（$3! = 6$ 种）并在每种顺序下贪心确定分界点是可行的。

算法步骤

1. 读入 $n$ 和三个数组 $a,b,c$，计算每个数组的前缀和 $preA, preB, preC$，以及总和 $tot = preA[n]$，需要值 $need = \lceil tot/3 \rceil$。
2. 对于六种全排列 $\pi$（表示第一个段给 $\pi_1$，第二个段给 $\pi_2$，第三个段给 $\pi_3$），执行以下操作：
   • 设当前指针 $cur = 1$。
   • 对 $i = 1,2,3$：
     • 在区间 $[cur, n]$ 内二分查找最小的位置 $pos$，使得前缀和 $pre_{\pi_i}[pos] - pre_{\pi_i}[cur-1] \ge need$。若找不到则失败。
     • 将 $cur$ 更新为 $pos+1$。
   • 如果成功找到三个位置 $pos_1, pos_2, pos_3$，则三个段分别为 $[1, pos_1]$, $[pos_1+1, pos_2]$, $[pos_2+1, pos_3]$（注意 $pos_3$ 可以是 $n$，即第三段可能直达末尾。实际上 $cur$ 最终会变成 $pos_3+1$，只需保证 $pos_3 \le n$ 且没有超过即可。因为第三个段需要覆盖到 $n$，所以要求 $pos_3 = n$？不，我们并没有强制第三段必须包含所有剩余块，但题目要求三个段分别是连续的并且不重叠，并没有要求它们必须覆盖整个数组？仔细阅读原题：“No piece is assigned to more than one person”即每块最多一人，但允许有些块没分给任何人？实际上，由于蛋糕总块数为 $n$，每人取一段连续区间，且不能重叠，那么剩下的块（如果有）就属于没分到的人。但题目要求每人获得一段，且三段不相交，但并未要求三段必须覆盖所有 $n$ 块。然而样例中，第一组数据输出 1 1 2 3 4 5，覆盖了全部 $5$ 块。第二组数据输出 5 6 1 2 3 4，覆盖了 $1$ 到 $6$ 全部块。可见，实际上所有块都必须被分配（因为每人一段连续且不相交，且总数 $n$ 等于三段的长度和？不一定，可以有一些不被任何段包含，但那样就没给任何人，不符合“分享”的直觉？题目并未明确要求所有块都必须分配，但按照常规理解，给每人一个连续切片，这些切片可能不覆盖全部蛋糕，剩余蛋糕可能被扔掉？原题表述：“give each person a contiguous slice of cake”并没说必须用完所有蛋糕，且约束只要求切片不相交。那么剩余的部分可以被丢弃。但为了最大化可行性，我们其实可以允许三段之间有空隙。然而在贪心过程中，我们实际上强制三段首尾相接，这是因为我们每次将 $cur$ 设为 $pos+1$，使得三段连续覆盖从 $1$ 到某个位置。这样最后一节可能没有覆盖到 $n$，但剩余块（$pos_3+1$ 到 $n$）没有被分配，这是允许的。实际上，我们只需要三段各自的和满足条件，且互不相交，它们不必覆盖整个数组。因此我们的贪心方法是正确的：每次都取满足条件的最短前缀，这样能留出更多空间给后面的段，而且最后一段可以不用管后面的剩余块。
   • 如果成功，则根据顺序 $\pi$ 将三个区间对应到 Alice, Bob, Charlie 的输出顺序，输出即可。
3. 若六种顺序均失败，输出 $-1$。

正确性证明

• 必要性：如果存在一组解，那么三个段在数组中的左右顺序必然对应某一种排列 $\pi$（即谁拿最左边、中间、最右边）。对于该排列，我们可以将三个段按照其在数组中的位置从左到右记为 $I_1, I_2, I_3$。我们现在证明，用上述贪心方法一定能找到一组解（不一定与原解相同）。这是因为：

  • 对于 $I_1$，其起始下标为 $1$（因为是最左边，如果原解中第一个段并非从 $1$ 开始，那么 $1$ 到 $I_1$ 左侧的块未被分配，我们可以直接将 $I_1$ 向左扩展（即包含前面未分配的块）不会减少 $I_1$ 在对应人估值上的和（因为所有 $a_i,b_i,c_i \ge 1$，扩展只会增加和），所以左端可以调整为 $1$ 而不破坏条件。因此我们总可以假设第一段从 $1$ 开始。
  • 然后，对于 $I_2$，其左端是 $I_1$ 右端加 $1$。在贪心过程中，我们选取的是满足条件的最短前缀（即最小的右端点）作为第一段。这个右端点不会大于原解中 $I_1$ 的右端点（因为原解右端点也满足条件，而最短前缀是满足条件的最小右端点，所以贪心找到的右端点 $\le$ 原解右端点）。由此，贪心第二段开始的位置 $cur = pos_1+1$ 不会晚于原解第二段开始位置，因此后续步骤同样可以找到满足条件的段（因为原解的第二段在贪心开始的更靠左的位置也能成立？实际上，原解第二段在更右边的位置，但贪心开始的更靠左，可能会更早达到所需和？我们需要谨慎：原解的第二段在其自己的起始位置满足和 $\ge need$，但贪心开始的位置更早，其前缀和可能更小（因为多包含了前面的一些块？实际上，贪心第二段从 $pos_1+1$ 开始，而原解第二段是从 $R_1+1$ 开始，其中 $R_1 \ge pos_1$。因为 $pos_1+1 \le R_1+1$，所以贪心第二段开始位置在原解第二段左侧。由于所有 $b_i$ 为正，左移开始位置会使前缀和变小（因为少了一些正数），所以原解第二段在当前位置不一定能满足条件。因此贪心可能失败。所以我们需要另一条思路：实际上，我们可以证明通过枚举所有顺序并采用最短前缀贪心能够找到解当且仅当解存在。这是一个经典结论：因为题目中所有值为正数，所以前缀和单调递增。如果我们固定排列顺序，那么贪心地为每个段取尽可能短的前缀（即刚好满足条件的右端点），这不会破坏后续段的可能性，因为这会为后续段留下更多的空间（更靠右的开始位置使得后续段更容易满足条件？实际上是留下更少的剩余长度，所以可能更困难）。正确的做法是贪心地取尽可能长的前缀？不，我们需要确保三个段的总长度不超过 $n$。通常的方法是先尝试所有排列，对每个排列，我们找第一个段满足条件的最右端点（即贪心取最小右端点），然后第二个段从下一个位置开始取最小右端点，第三个段取剩余部分并检查是否满足条件。这样是安全的，因为如果我们第一个段取更大的右端点，那么留给后面两个段的区间更短，更难满足条件，所以取最小右端点是最优的。因此，若存在解，则贪心取最小右端点也能找到一组解（否则，如果所有最小右端点都无法让后面满足，那么任何更大右端点更不可能）。这个论证是标准的，类似于“在正数序列中找几个和至少为某值的子段”的贪心策略。因此算法正确。

• 充分性：若贪心在某排列下成功找到三段，则直接得到一组符合要求的解。

复杂度分析

• 对每个测试用例，计算前缀和 $O(n)$。
• 对每种排列（6种），进行三次二分查找（每次 $O(\log n)$），总 $O(6 \cdot 3 \cdot \log n) = O(\log n)$ 常数很小。
• 总复杂度 $O(n + \log n)$，主要开销在读取数据和前缀和计算。所有测试用例的 $n$ 之和不超过 $2\times 10^5$，因此非常快。

实现细节与注意事项

• 由于需要二分查找最小位置使得前缀和差 $\ge need$，可使用 lower_bound 或手写二分。
• 注意前缀和数组使用 long long 避免溢出（$n \cdot 10^6 \le 2\times 10^{11}$ 在 64 位内安全）。
• 当 $need = 0$ 时（例如 $tot < 3$ 但 $tot$ 至少为 $n$，且 $n\ge 3$，每个 $a_i\ge 1$，故 $tot \ge 3$，所以 $need \ge 1$），但本题 $a_i \ge 1$，因此 $need \ge 1$ 可直接处理。
• 在二分查找时，若找不到满足条件的位置，说明该排列不可行。
• 输出时按照 Alice, Bob, Charlie 的顺序输出六个整数，即 $l_a, r_a, l_b, r_b, l_c, r_c$，无论我们在贪心时使用了何种排列顺序，最后需要映射回原始三个人。

示例解析

以第一个测试用例为例： $a = [5,1,1,1,1]$, $b = [1,1,5,1,1]$, $c = [1,1,1,1,5]$, $tot=9$, $need=3$。 尝试排列 $(Alice, Bob, Charlie)$：

• 第一段给 Alice：从位置1起找最小右端使得和 $\ge 3$，$a_1=5\ge 3$，所以 $pos_1=1$。
• 第二段从2开始给 Bob：前缀和 $b$ 在位置2处和 $=1$，位置3处 $=1+5=6\ge 3$，所以 $pos_2=3$。
• 第三段从4开始给 Charlie：$c_4=1$, $c_5=5$，到位置5和 $=1+5=6\ge 3$，$pos_3=5$。 成功，输出 $l_a=1,r_a=1; l_b=2,r_b=3; l_c=4,r_c=5$。

总结

本题的关键在于将三个连续子段的分配问题转化为枚举谁拿左边、中间、右边，然后对每种顺序使用贪心法（每次取满足条件的最短前缀）来判断可行性。由于所有数均为正，前缀和单调递增，贪心策略是安全的。算法时间复杂度线性，代码实现简洁，是 Codeforces 上常见的“三段覆盖”类问题的标准解法。