← 返回题目列表

Codeforces · 2067/B

B. 两个大包

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

你有两大袋数字。最初,第一个袋子包含 $$$n$$$ 数字:$$$a_1, a_2, \ldots, a_n$$$,而第二个袋子是空的。您可以执行以下操作:

- 从第一个袋子中选择任意数字并将其移至第二个袋子中。
- 从第一个袋子中选择一个也存在于第二个袋子中的数字,并将其加一。

您可以按任何顺序执行无限数量的这两种类型的操作。是否可以使第一袋和第二袋的内容相同?

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 数组 $$$a$$$ 的长度。保证 $$$n$$$ 是偶数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

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

输出

对于每个测试用例,如果可以均衡袋子中的内容,请打印“YES”。否则,输出“NO”。

您可以在任何情况下输出每个字母(例如,“YES”、“Yes”、“yes”、“yEs”、“yEs”将被识别为肯定答案)。

示例

输入 #1

9
2
1 1
2
2 1
4
1 1 4 4
4
3 4 3 3
4
2 3 4 4
6
3 3 4 5 3 3
6
2 2 2 4 4 4
8
1 1 1 1 1 1 1 4
10
9 9 9 10 10 10 10 10 10 10

输出 #1

Yes
No
Yes
Yes
No
Yes
No
Yes
Yes

注意

让我们分析第六个测试用例:我们将展示导致袋子相等的操作顺序。最初,第一个袋子由数字 $$$(3, 3, 4, 5, 3, 3)$$$ 组成,第二个袋子是空的。

1. 在第一个操作中,将数字 $$$3$$$ 从第一个袋子移动到第二个袋子。状态:$$$(3, 4, 5, 3, 3)$$$ 和 $$$(3)$$$。
2. 在第二次操作中,将第一个包中的数字$$$3$$$ 加一。此操作之所以可行,是因为第二个包包含数字 $$$3$$$。状态:$$$(4, 4, 5, 3, 3)$$$ 和 $$$(3)$$$。
3. 在第三个操作中,将数字 $$$4$$$ 从第一个袋子移动到第二个袋子。状态:$$$(4, 5, 3, 3)$$$ 和 $$$(3, 4)$$$。
4. 在第四次操作中,将第一个包中的数字$$$4$$$ 加一。状态:$$$(5, 5, 3, 3)$$$ 和 $$$(3, 4)$$$。
5. 在第五次操作中,将数字 $$$5$$$ 从第一个袋子移动到第二个袋子。状态:$$$(5, 3, 3)$$$ 和 $$$(3, 4, 5)$$$。
6. 在第六次操作中,将第一个包中的数字$$$3$$$ 加一。州:$$$(5, 3, 4)$$$ 和 $$$(3, 4, 5)$$$。

正如我们所看到的,通过这些操作,可以使袋子中的内容相等,因此答案存在。