← 返回题目列表

Codeforces · 1747/A

A. 两组

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您希望将这些 $$$n$$$ 整数分配到两个组 $$$s_1$$$ 和 $$$s_2$$$(组可以为空),以便满足以下条件:

- 对于每个 $$$i$$$ $$$(1 \leq i \leq n)$$$,$$$a_i$$$ 恰好属于一组。
- 值 $$$|sum(s_1)| - |sum(s_2)|$$$ 是所有此类分配整数的方式中可能的最大值。这里 $$$sum(s_1)$$$ 表示组 $$$s_1$$$ 中的数字之和,$$$sum(s_2)$$$ 表示组 $$$s_2$$$ 中的数字之和。

确定 $$$|sum(s_1)| 的最大可能值- |总和(s_2)|$$$。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^4)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2 \ldots a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — 数组 $$$a$$$ 的元素。

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

输出

对于每个测试用例,输出一个整数 - $$$|sum(s_1)| 的最大可能值- |总和(s_2)|$$$。

示例

输入 #1

4
2
10 -10
4
-2 -1 11 0
3
2 3 2
5
-9 2 0 0 -4

输出 #1

0
8
7
11

注意

在第一个测试用例中,我们可以分布为 $$$s_1 = \{10\}$$$, $$$s_2 = \{-10\}$$$。那么该值将是 $$$|10| - |-10| = 0$$$。

在第二个测试用例中,我们可以分布为 $$$s_1 = \{0, 11, -1\}$$$, $$$s_2 = \{-2\}$$$。那么该值将是 $$$|0 + 11 - 1| - |-2| = 10 - 2 = 8$$$。

在第三个测试用例中,我们可以分布为 $$$s_1 = \{2, 3, 2\}$$$, $$$s_2 = \{\}$$$。那么该值将是 $$$|2 + 3 + 2| - |0| = 7$$$。

在第四个测试用例中,我们可以分布为 $$$s_1 = \{-9, -4, 0\}$$$, $$$s_2 = \{2, 0\}$$$。那么该值将是 $$$|-9 - 4 + 0| - |2 + 0| = 13 - 2 = 11$$$。