← 返回题目列表

Codeforces · 1405/B

B. 阵列取消

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,使得 $$$a_1 + a_2 + \cdots + a_n = 0$$$。

在一次操作中,可以选择两个不同的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$),$$$a_i$$$ 减 1,$$$a_j$$$ 加 1。如果 $$$i < j$$$ 这个操作是免费的,否则需要花费一枚硬币。

你需要花费多少金币才能使所有元素等于$$$0$$$?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 元素的数量。

下一行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。已知 $$$\sum_{i=1}^n a_i = 0$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印我们必须花费的最小硬币数量,以使所有元素等于 $$$0$$$。

示例

输入 #1

7
4
-3 5 -3 1
2
1 -1
4
-3 2 -3 4
4
-1 1 1 -1
7
-5 7 -6 -4 17 -13 4
6
-1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000
1
0

输出 #1

3
0
4
1
8
3000000000
0

注意

第一个测试用例的可能策略:

- 执行 $$$(i=2, j=3)$$$ 三次(免费),$$$a = [-3, 2, 0, 1]$$$。
- 执行 $$$(i=2, j=1)$$$ 两次(支付两个硬币),$$$a = [-1, 0, 0, 1]$$$。
- 执行 $$$(i=4, j=1)$$$ 一次(支付一枚硬币),$$$a = [0, 0, 0, 0]$$$。