CF1918D Blocking Elements

给定一个数组 $a_1, a_2, \ldots, a_n$，你的任务是阻断数组中的一些元素，使得数组的代价最小。假设你阻断了下标为 $1 \leq b_1 < b_2 < \ldots < b_m \leq n$ 的元素，则数组的代价定义为以下两者的最大值： - 被阻断元素的和，即 $a_{b_1} + a_{b_2} + \ldots + a_{b_m}$。 - 当移除被阻断的元素后，数组被分成 $(m+1)$ 个连续子段，这些子段的最大和。具体来说，这些子段为：$[1, b_1-1]$，$[b_1+1, b_2-1]$，$\ldots$，$[b_{m-1}+1, b_m-1]$，$[b_m+1, n]$（如果子段形如 $[x, x-1]$，则其和视为 $0$）。 例如，如果 $n=6$，原数组为 $[1, 4, 5, 3, 3, 2]$，你阻断了第 $2$ 和第 $5$ 个位置的元素，则数组的代价为被阻断元素之和（$4+3=7$）与各子段的和（$1$，$5+3=8$，$2$）中的最大值，即 $\max(7,1,8,2)=8$。 你需要输出阻断数组后最小的代价。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 30000$），表示询问的数量。 每个测试用例包含两行。第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示阻断数组后的最小代价。

第一个测试用例与题目描述中的数组一致。要得到代价 $7$，你需要阻断第 $2$ 和第 $4$ 个位置的元素。此时，数组的代价为以下两者的最大值： - 被阻断元素的和，即 $a_2 + a_4 = 7$。 - 移除被阻断元素后，数组被分成的各段的最大和，即 $a_1$，$a_3$，$a_5 + a_6 = \max(1,5,5) = 5$。 因此，代价为 $\max(7,5) = 7$。 在第二个测试用例中，你可以阻断第 $1$ 和第 $4$ 个位置的元素。 在第三个测试用例中，要得到答案 $11$，你可以阻断第 $2$ 和第 $5$ 个位置。还有其他方式也可以得到同样的答案，例如阻断第 $4$ 和第 $6$ 个位置。 由 ChatGPT 4.1 翻译