B. Two Large Bags 详细题解

问题理解

有两个袋子，初始时第一个袋子有 $n$ 个数（$n$ 为偶数），第二个袋子为空。允许两种操作：

1. 将任意一个数从第一个袋子移动到第二个袋子
2. 如果第一个袋子中有一个数 $x$ 也在第二个袋子中存在，则可以将这个 $x$ 增加 $1$（变成 $x+1$）

目标：经过若干次操作，使两个袋子的内容完全相同（即所有数及出现次数都相同）。

---

关键观察

1. 最终状态：由于总数字个数不变（移动不改变总数，增加操作也不改变个数），最终两个袋子各有 $n/2$ 个数。

2. 操作的本质：

   • 操作 1 只是转移数字
   • 操作 2 相当于：利用第二个袋子中已有的某个值 $x$，可以将第一个袋子中的一个 $x$ 升级为 $x+1$

3. 数字的变化方向：数字只能通过操作 2 增加，不能减少。因此，初始值较小的数有机会变大，但初始值较大的数无法变小。

---

转化问题

设 $cnt[x]$ 表示初始时第一个袋子中值为 $x$ 的个数。
最终，第一个袋子会有 $n/2$ 个数，第二个袋子也有 $n/2$ 个数，且两个袋子的多重集相等。

这意味着：最终所有数会分成相等的两份。由于操作只能把数变大，最小的数会留在第一个袋子还是第二个？需要仔细分析。

实际上，更自然的想法是：考虑所有数从小到大排列。由于只能增加，大数无法变小，所以如果要分成两个相等的多重集，必须保证每个数最终出现的次数符合某种平衡。

---

标程的贪心方法

标程采用了非常巧妙的贪心：

1. 统计每个数值的出现次数 cnt[i]
2. 从小到大遍历数值 $i = 1$ 到 $n$：
   • 如果 cnt[i] 是奇数，则不可能（因为总个数 $n$ 是偶数，但分布会出问题？）
   • 实际上，标程检查的是：如果 cnt[i] == 1，直接判定为 NO
   • 否则，将 cnt[i] - 2 个多余的数“进位”到 cnt[i+1]

为什么这样？

---

原理

考虑数字 $i$：

• 在最终的两个袋子中，数字 $i$ 必须出现偶数次（因为两个袋子相等，每个袋子中 $i$ 出现 $k$ 次，则总共 $2k$ 次）
• 初始时 cnt[i] 可能为奇数。但通过操作，我们可以把一些 $i$ 变成 $i+1$（前提是第二个袋子中有一个 $i$）

关键点：每个数字 $i$ 要能发生“升级”，必须先在第二个袋子中有一个 $i$。这要求我们在处理 $i$ 之前，已经通过某种方式将一些 $i$ 移到了第二个袋子。

标程的贪心逻辑是：

• 从左到右处理数值 $i$
• 每次保留 2 个 $i$（一个给第一个袋子，一个给第二个袋子），剩下的 cnt[i] - 2 个 $i$ 都“升级”成 $i+1$
• 如果 cnt[i] == 1，则无法配对（因为需要 2 个才能分别放入两个袋子），直接失败
• 升级后，cnt[i+1] 增加 cnt[i] - 2

---

为什么只保留 2 个？

因为最终每个数字在第一个袋子中出现 $k$ 次，第二个袋子中也出现 $k$ 次，总共 $2k$ 次。
对于最小的数字，它只能通过升级变大，不能减小。所以为了匹配，每个数字最终出现的总次数必须是偶数。

如果我们保留 $2$ 个 $i$，那么这两个 $i$ 可以一个放在第一个袋子，一个放在第二个袋子，形成匹配。其余的都升级成 $i+1$，以便与更大的数匹配。

---

最终条件

按照上述贪心过程：

• 如果遇到某个 cnt[i] 为奇数且不等于 1（比如 3,5,7...），实际上奇数的 cnt[i] 在经过保留 2 个后，剩下的 cnt[i]-2 是奇数，升级后传递给 i+1，最终会导致某个位置出现 1 个无法配对的数。
• 标程只判断 cnt[i] == 1 就失败，而没有直接判断奇数，为什么？

因为 cnt[i] 是奇数且 > 1 时，例如 3，保留 2 个，剩下 1 个升级到 i+1，此时 cnt[i+1] 增加 1，可能变成偶数或奇数。只要最终不出现 1，就有机会成功。所以判断奇数并不直接导致失败。

实际上，正确的终止条件是：当遍历完所有 $i$ 后，cnt[n+1] 必须为 0（因为数值不能超过 $n$，$a_i \le n$）。
但标程没有显式检查，而是依赖 cnt[i]==1 的检测。

---

示例验证

例 1: [1,1]

• cnt[1]=2，保留 2 个，剩 0，升级 0 到 cnt[2]
• 结束，没有出现 1 → YES

例 2: [2,1] (即 cnt[1]=1, cnt[2]=1)

• i=1: cnt[1]==1 → NO

例 3: [1,1,4,4]

• cnt[1]=2 → 保留 2，剩 0
• cnt[4]=2 → 保留 2，剩 0
• 无 1 → YES

例 4: [3,4,3,3] (即 cnt[3]=3, cnt[4]=1)

• i=1,2: cnt=0
• i=3: cnt=3，保留 2，剩 1 → 升级到 cnt[4]，cnt[4] 变成 1+1=2
• i=4: cnt=2，保留 2，剩 0
• 无 1 → YES

例 5: [2,3,4,4]

• cnt[2]=1 → NO

与输出一致

---

复杂度

• 统计频率 $O(n)$
• 遍历数值 $O(n)$
• 每个测试用例 $O(n)$，总 $O(\sum n) \le O(\sum n^2) \le 10^6$，可行

---

总结

这道题的核心是：

1. 将问题转化为数值的“配对”与“升级”
2. 贪心处理：每个数值保留 2 个（分别给两个袋子），其余都升级到下一个数值
3. 如果某个数值出现次数为 1，则无法配对 → NO
4. 否则，最终可以成功

这种贪心策略巧妙地利用了操作 2 的“升级”功能，以及“最终两个袋子相等”要求每个数值出现偶数次的性质。