原题链接：点击这里访问
题目描述 #
贝茜和埃尔茜发现了一行 \(N\) 个蛋糕（\(N\) 为偶数），大小依次为 \(a_1, a_2, \dots, a_N\)。
两头奶牛都想吃到尽可能多的蛋糕。但是，作为非常文明的奶牛，她们决定玩一个游戏来分割蛋糕！
游戏在两头奶牛之间轮流进行回合。
每个回合进行以下两者之一：
- 贝茜 选择两个相邻的蛋糕并将它们堆叠起来，制造大小为两者大小之和的一个新蛋糕。
- 埃尔茜 选择最左边或最右边的蛋糕藏起来。
当只剩下一个蛋糕时，贝茜吃掉它，而埃尔茜吃掉她藏起来的所有蛋糕。
如果两头奶牛都采取最优策略以最大化她们吃到的蛋糕量，并且贝茜先进行回合，那么每头奶牛将会吃到多少蛋糕？
输入格式
每个测试点包含 \(T\) 个独立的测试用例。
每个测试用例的格式如下：
- 第一行包含整数 \(N\)。
- 第二行包含 \(N\) 个空格分隔的整数 \(a_1, a_2, \dots, a_N\)。
输出格式
对于每个测试用例，输出一行，包含两个整数 (b) 和 (e)，表示贝茜和埃尔茜在两头奶牛都采取最优策略的情况下分别吃到的蛋糕量。
数据范围
- \(1 \leq T \leq 10\)
- \(2 \leq N \leq 5 \times 10^5\)
- \(1 \leq a_i \leq 10^9\)
- 输入保证一个测试点中的所有 \(N\) 之和不超过 \(10^6\)。
输入样例
2
4
40 30 20 10
4
10 20 30 40
输出样例
60 40
60 40
样例解释
对于第一个测试用例，在最优策略下：
- 贝茜将堆叠中间两个蛋糕。现在蛋糕的大小为
[40, 50, 10]。 - 埃尔茜将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为
[50, 10]。 - 贝茜堆叠剩余的两个蛋糕。
最终，贝茜将吃到 \(30+20+10=60\) 的蛋糕，而埃尔茜将吃到 \(40\) 的蛋糕。
第二个测试用例是第一个测试用例反转的情况，因此答案相同。
解题思路 #
根据数据规模可知时间复杂度最多支持 nlogn
因此可以排除 博弈论 和 动态规划（DP） 这类通常需要 O(n²) 或更高复杂度的解法。我们需要找到更优的解法，如 贪心 或 二分查找 + 前缀和 等方法。
因此想去找博弈通解：
-
埃尔茜只能吃 n // 2 - 1 个
-
埃尔茜每次都会吃当前左右两边中最小的蛋糕
-
贝茜的最优策略是不合并靠近左右边界的蛋糕
这样可以让埃尔茜的选择变得更有限，从而使她的总得分尽可能小
-
因此贝茜吃到的是连续 n // 2 + 1 个蛋糕的最小和
-
o1区间求和 -> 前缀和
题解 #
import math
t = int(input())
while t > 0:
t -= 1 # python 循环输入不能写 while t -= 1
n = int(input())
arr = list(map(int, input().split()))
sum_arr = sum(arr)
sum_min = math.inf
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + arr[i - 1]
for i in range(n // 2 + 1, n + 1):
sum_min = min(sum_min, prefix[i] - prefix[i - n // 2 - 1])
# print("@", sum_min)
print(sum_min, sum_arr - sum_min)