P14981 [USACO26JAN1] Milk Buckets G

Bessie 向 Farmer John 发起了一个涉及牛奶桶的游戏挑战！有 $N$ 个（$2 \leq N \leq 2 \cdot 10^5$）牛奶桶排成一行。从左数第 $i$ 个桶最初装有 $a_i$（$0 \leq a_i \leq 10^9$）加仑牛奶。 游戏分为两个阶段： 阶段 1：Farmer John 可以交换任意两个相邻的桶。他可以执行任意多次交换，但每次交换需要花费 1 枚硬币。 阶段 2：交换完成后，Farmer John 执行以下操作，直到只剩下一个桶为止：选择两个相邻的桶，其牛奶量分别为 $a_i$ 和 $a_{i+1}$，并将这两个桶替换为一个桶，新桶中装有 $\frac{a_i+a_{i+1}}2$ 加仑牛奶，放在它们原来的位置。 你的目标是确定在交换阶段中，Farmer John 必须花费的最小硬币数量，以便在所有合并完成后，最终桶中的牛奶量最大化。

第一行包含一个整数 $T$（$1 \leq T \leq 100$）：独立测试用例的数量。 接下来，对于每个测试用例，第一行包含一个整数 $N$：牛奶桶的数量。第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，用空格分隔：每个桶中牛奶的加仑数。 保证所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出 Farmer John 为了最大化最终桶中的牛奶量而必须花费的最小硬币数量。

对于第一个测试用例，我们在第一阶段不需要交换任何牛奶桶。在第二阶段，Farmer John 可以合并前两个桶，然后合并剩下的两个桶，最终得到 $0.5$ 加仑的牛奶。可以证明，这个最终量是最大的。 对于第二个测试用例，我们必须在第一阶段交换前两个牛奶桶一次，才能在第二阶段得到 $0.5$ 加仑的最终量。可以证明，如果不在第一阶段进行交换，我们无法达到 $0.5$ 加仑的最终量。 --- 对于第一个测试用例，Farmer John 可以在第一阶段交换第二个和第三个桶。然后，在第二阶段，Farmer John 可以执行以下操作： - $[9,9,4,2]$ -> 合并第三和第四个桶 -> - $[9,9,3]$ -> 合并第二和第三个桶 -> - $[9,6]$ -> 合并第一和第二个桶 -> - $[7.5]$ 最终的牛奶量为 $7.5$，这是可能的最大值。可以证明，即使进行更多的交换，最终量也无法超过 $7.5$，而如果交换次数更少，最终量也无法达到 $7.5$。 --- - 输入 $3$-$4$：$a_i\le 1$ 且 $N\le 2000$（$N$ 之和 $\le 5000$） - 输入 $5$-$6$：$a_i\le 1$ - 输入 $7$-$9$：$N\le 2000$（$N$ 之和 $\le 5000$） - 输入 $10$-$14$：无额外约束。 翻译由 DeepSeek V3 完成