「JOI 2014 Final」年轮蛋糕 题解

问题分析

我们有一个环形蛋糕，总共有 $N$ 个切口，将蛋糕分成 $N$ 块，每块大小为 $A_i$。我们需要在环形蛋糕上切 $3$ 刀（只能在切口位置），将蛋糕分成 $3$ 块，目标是最大化最小块的大小。

这是一个典型的最大化最小值问题，可以使用二分答案来解决。

解题思路

1. 环形数组处理

由于蛋糕是环形的，我们将其复制一份接在后面，形成长度为 $2N$ 的数组，这样可以方便地处理环形情况。

vector<int> a(m + 1);
for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i + n] = a[i];  // 环形复制
}

2. 二分答案框架

我们二分查找可能的最小块的最大值 $x$：

• 如果存在一种切法使得三块蛋糕的大小都 $\geq x$，那么 $x$ 是可行的，尝试更大的值
• 否则，$x$ 不可行，需要减小

long long l = 0, r = 1e15, ans = 0;
while (l <= r) {
    long long mid = (l + r) >> 1;
    if (check(mid)) {
        ans = mid;
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

3. Check 函数的核心逻辑

check(val) 函数判断是否存在一种切法，使得三块蛋糕的大小都至少为 $val$。

3.1 预处理 R 数组

对于每个起始位置 $i$，计算 $R[i]$ 表示从 $i$ 开始，累加蛋糕块直到总和 $\geq val$ 时的下一个位置：

vector<int> R(m + 1);
long long sum = 0;
for (int l = 1, r = 1; l <= m; l++) {
    while (r <= m && sum < val) {
        sum += a[r];
        r++;
    }
    R[l] = r;  // 从l开始，到r-1结束的区间和 >= val
    sum -= a[l];
}

3.2 检查可行性

对于每个可能的起始位置 $i$（$1 \leq i \leq N$），我们尝试切三刀：

1. 第一刀在位置 $i$，第二刀在 $R[i]$，第三刀在 $R[R[i]]$
2. 检查这三刀是否都在环形范围内（不超过 $i + N$）

for (int i = 1; i <= n; i++) {
    int to = R[i];        // 第一段结束位置
    if (to > i + n) continue;
    
    to = R[to];           // 第二段结束位置  
    if (to > i + n) continue;
    
    to = R[to];           // 第三段结束位置
    if (to > i + n) continue;
    
    return true;          // 找到可行解
}

如果存在这样的 $i$，说明可以找到三刀使得每块大小都 $\geq val$。

算法正确性证明

1. 二分答案的正确性

设最优解为 $opt$，那么：

• 对于所有 $x \leq opt$，都存在切法使得最小块 $\geq x$
• 对于所有 $x > opt$，都不存在这样的切法

因此二分框架可以正确找到 $opt$。

2. Check 函数的正确性

对于固定的起始位置 $i$：

• $R[i]$ 保证了第一块蛋糕大小 $\geq val$
• $R[R[i]]$ 保证了第二块蛋糕大小 $\geq val$
• $R[R[R[i]]]$ 保证了第三块蛋糕大小 $\geq val$

由于环形复制，我们只需要检查 $i$ 从 $1$ 到 $N$ 的所有可能起始位置。

复杂度分析

• 预处理前缀和：$O(N)$
• 二分答案：$O(\log(\sum A_i))$ 次迭代
• 每次 Check：$O(N)$（预处理 R 数组）+ $O(N)$（检查所有起始位置）
• 总复杂度：$O(N \log(\sum A_i))$

对于 $N \leq 10^5$，这个复杂度是可以接受的。

示例验证

样例 1

输入：

6
1
5
4
5
2
4

处理过程：

1. 环形复制：[1,5,4,5,2,4,1,5,4,5,2,4]
2. 二分查找，最终找到答案 $6$
3. 验证：从位置 $1$ 开始切，三刀分别在位置 $1,3,5$，得到的三块大小为：
   • 块1: $1+5 = 6$
   • 块2: $4+5 = 9$
   • 块3: $2+4 = 6$ 最小块大小为 $6$

总结

本题通过以下技巧解决了环形蛋糕分割问题：

1. 环形数组复制处理环形结构
2. 二分答案框架解决最大化最小值问题
3. 双指针预处理快速计算满足条件的区间端点
4. 贪心检查验证二分答案的可行性

这种方法高效且正确，能够在规定时间内解决大规模数据。