Codeforces Round 1004（Div.2） B. Two Large Bags 补题 + 题解 python

B. Two Large Bags

https://codeforces.com/contest/2067/problem/B

题目描述

time limit per test: 1 second
memory limit per test: 256 megabytes

You have two large bags of numbers. Initially, the first bag contains $n$ numbers: $a_1, a_2, \ldots, a_n$ , while the second bag is empty. You are allowed to perform the following operations:

Choose any number from the first bag and move it to the second bag.
Choose a number from the first bag that is also present in the second bag and increase it by one.

You can perform an unlimited number of operations of both types, in any order. Is it possible to make the contents of the first and second bags identical?

大致题意:

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

-从第一个袋子中选择任意数字并将其移动到第二个袋子中。

-从第一个袋子中选择一个数字，这个数字也出现在第二个袋子中，然后加1。

您可以以任意顺序执行这两种类型的无限数量的操作。第一个袋子和第二个袋子的内容物是否可以完全相同？

Input

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

The first line of each test case contains an integer $n$ ( $\le n \le 1000$ ) — the length of the array $a$ . It is guaranteed that $n$ is an even number.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $\le a_i \le n$ ).

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^6$ .

输入

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

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

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

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

Output

For each test case, print “YES” if it is possible to equalize the contents of the bags. Otherwise, output “NO”.

You can output each letter in any case (for example, “YES”, “Yes”, “yes”, “yEs”, “yEs” will be recognized as a positive answer).

输出

对于每个测试用例，如果可以平衡袋子的内容，则打印“YES”。否则输出“NO”。
您可以在任何情况下输出每个字母(例如，“YES”，“YES”，“YES”，“YES”，“YES”将被识别为肯定答案)。

Example

Input

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

Output

Yes
No
Yes
Yes
No
Yes
No
Yes
Yes

Note

Let’s analyze the sixth test case: we will show the sequence of operations that leads to the equality of the bags. Initially, the first bag consists of the numbers $(3, 3, 4, 5, 3, 3)$ , and the second bag is empty.

In the first operation, move the number $3$ from the first bag to the second. State: $(3, 4, 5, 3, 3)$ and $(3)$ .
In the second operation, increase the number $3$ from the first bag by one. This operation is possible because the second bag contains the number $3$ . State: $(4, 4, 5, 3, 3)$ and $(3)$ .
In the third operation, move the number $4$ from the first bag to the second. State: $(4, 5, 3, 3)$ and $(3, 4)$ .
In the fourth operation, increase the number $4$ from the first bag by one. State: $(5, 5, 3, 3)$ and $(3, 4)$ .
In the fifth operation, move the number $5$ from the first bag to the second. State: $(5, 3, 3)$ and $(3, 4, 5)$ .
In the sixth operation, increase the number $3$ from the first bag by one. State: $(5, 3, 4)$ and $(3, 4, 5)$ .

As we can see, as a result of these operations, it is possible to make the contents of the bags equal, so the answer exists.

注意

让我们分析第六个测试用例：我们将展示导致袋子相等的操作序列。
最初，第一个袋子由数字(3,3,4,5,3,3)组成，第二个袋子是空的。
1.在第一个操作中，将编号3从第一个袋子移动到第二个袋子。状态：(3,4,5,3,3)和(3)
2.在第二个操作中，将第一个包的编号3增加1。这个操作是可能的，因为第二个包包含数字3。状态：（4,4,5,3,3)和(3)
3.在第三个操作中，将数字4从第一个袋子移动到第二个袋子。状态：(4,5,3,3)和(3,4)。
4.在第四个操作中，将第一个包的编号4增加1。状态：(5,5,3,3)和(3,4)。
5.在第五个操作中，将数字5从第一个包移动到第二个包。状态：(5,3,3)和(3,4,5)。
6.在第六次操作中，将第一个袋子的数字3加1。状态：(5,3,4)和(3,4,5)。

正如我们所看到的，作为这些操作的结果，可以使袋子的内容相等，因此答案是存在的。

思路分析

初始条件：第一个袋子包含数组a，第二个袋子为空。
操作：
- 将一个数字从第一个袋子移到第二个袋子。
- 将第一个袋子中的某个数字加1（前提是该数字已经在第二个袋子中）。

贪心思路：

每次我们发送一个数字到第二个袋子时，如果我们想要平衡，那么在操作结束时，第一个袋子里必须保留一个相等的数字。我们将第一个包中的这个相等的数字称为“blocked”：不应该再对它执行任何操作。

事实证明，在可能的情况下使用第二个操作总是最优的，而不计算“阻塞”的数字。也就是说，将第一个包中所有相等的 a1数字加1。然后继续处理同样的问题。

为什么呢？假设我们在第一个袋子中保留一些相等的 a1 数，而不增加它们。然后，按照同样的逻辑，我们必须将其中一个转移到第二个袋子中，阻塞相同数量的第一个袋子。但是，如果我们将两个数字都增加 1 ，它们仍然相等，并且仍然可以选择将其中一个转移到第二个袋子中，并将相等的一个放在第一个袋子中。此外，等于 a1 的数字已经在第二个包中。
因此，对所有剩余的等于a1 数选择加1是最优的。然后继续处理数组 a3,a4,…,an 的问题，其中所有的数字都是 >a1 ，这个问题已经可以用类似的方法解决了。
声明：思路来自https://codeforces.com/blog/entry/139415?locale=en

code实现

from collections import Countert = int(input())
for _ in range(t):n = int(input())a = list(map(int, input().split()))flag = 1cnt = Counter(a)  # 计数for i in range(max(a) + 1):if cnt[i] > 2:cnt[i + 1] += cnt[i] - 2  cnt[i] = 2# 总是选择操作2，所有等于ai的数加1，即cnt[i]留下两个，其余推入cnt[i+1]for i in range(max(a) + 1):if cnt[i] % 2 == 1:  # 奇数表示未完全配对flag = 0breakif flag == 0:print("No")else:print("Yes")