A16626 | $Game on Array$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的正整数数组 $a$。Alice 和 Bob 轮流玩游戏，Alice 先手。 每一次操作，当前玩家必须选择一个在数组 $a$ 中至少出现一次的值 $x>0$。然后： 1. 该玩家将获得与数组中 $x$ 的出现次数相等的分数。 2. 数组中所有等于 $x$ 的元素都减少 $1$，即变为 $x-1$。 注意，只有当 $x$ 在当前数组中存在时才能被选择，因此每一步操作都能获得正数的分数。例如，如果数组是 $[3,8,5,8]$，Alice 选择 $x=8$，数组就变为 $[3,7,5,7]$，Alice 获得 $2$ 分。游戏在数组所有元素都变为 $0$ 时结束。 假设两人都采取最优策略并希望最大化自己的得分，求最终 Alice 和 Bob 的得分。

输入包含多组测试数据。第一行为测试用例个数 $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$。

对于每个测试用例，输出两个整数，分别表示在两人都采取最优策略的情况下，Alice 和 Bob 的得分。

输入 #1

输出 #1

3 1
10 9
20 16

C++ 编辑器

输入

输出