CF2147D.Game on Array

You are given an array $a$ of $n$ positive integers. Alice and Bob will play a game with this array. They will take alternating turns, with Alice going first.

At each turn, the player must choose a value $x \gt 0$ that appears in $a$ at least once. Then,

1. the player earns $1$ point for each value $x$ in the array,
2. each value $x$ in the array is decreased by $1$ and becomes $x-1$.

Note that the player can choose $x$ only if it is present in $a$ at the moment, so each valid move earns a positive amount of points. For example, if the array is $[3,8,5,8]$ and Alice chooses $x=8$, the array will become $[3,7,5,7]$ and Alice will earn $2$ points.

The game ends when no $x$ can be chosen; that is, when all the elements in the array are zero.

Given that both players want to maximize their points and play optimally, calculate the amount of points that each player will end up with.

给你一个包含 $n$ 个正整数的数组 $a$。Alice 和 Bob 将用这个数组进行一场游戏。他们将轮流行动，Alice 先手。

在每一轮中，当前玩家必须选择一个值 $x \gt 0$，该值至少在数组 $a$ 中出现一次。然后：

1. 当前玩家对数组中每一个值为 $x$ 的元素获得 $1$ 分；
2. 数组中每一个值为 $x$ 的元素均减 $1$，变为 $x-1$。

注意：玩家只能选择当前存在于数组 $a$ 中的 $x$，因此每一次合法操作都必然获得正数分数。例如，若数组为 $[3,8,5,8]$，且 Alice 选择了 $x=8$，则数组将变为 $[3,7,5,7]$，Alice 将获得 $2$ 分。

当无法再选择任何 $x$（即数组中所有元素均为 $0$）时，游戏结束。

假设双方均希望最大化自己的得分，且均以最优策略进行游戏，请计算双方最终各自获得的分数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2\cdot 10^{5}$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^{9}$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^{5}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot 10^{5}$）—— 数组的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{9}$）—— 数组的元素。

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

For each test case, output two integers, the amount of points Alice and Bob will get if both play optimally.

对于每个测试用例，输出两个整数，分别表示爱丽丝和鲍勃在双方均采取最优策略时各自获得的分数。

Visualizer link

In the first test case, Alice chooses $x=1$ with her first move. The array becomes $[2,0,0]$ and she earns $2$ points. After that, Bob is forced to choose $x=2$. The array becomes $[1,0,0]$ and Bob earns $1$ point. Finally, Alice is forced to choose $x=1$ and earn one more point. After that, the array is $[0,0,0]$, so the game ends. In total, Alice finishes with $3$ points and Bob with $1$ point.

In the third test case, each player will decrement all the elements and earn $4$ points each move. Alice will earn $5 \cdot 4 = 20$ points while Bob will only earn $4\cdot 4 = 16$ points.

可视化链接

在第一个测试用例中，Alice 第一步选择 $x=1$。数组变为 $[2,0,0]$，她获得 $2$ 分。随后，Bob 被迫选择 $x=2$。数组变为 $[1,0,0]$，Bob 获得 $1$ 分。最后，Alice 被迫选择 $x=1$ 并再获得 $1$ 分。此后，数组变为 $[0,0,0]$，游戏结束。最终，Alice 共获得 $3$ 分，Bob 获得 $1$ 分。

在第三个测试用例中，每位玩家每步都将所有元素减 $1$，并各获得 $4$ 分。Alice 将获得 $5 \cdot 4 = 20$ 分，而 Bob 仅获得 $4\cdot 4 = 16$ 分。