Codeforces Round 858 (Div. 2) B. Mex Master

zsxuan / 2023-09-05 / 原文

给一个长为 $n$ 的数组 $a$ ，定义 $a$ 的 $score$ 为 $a_1+ a_2, a_2 + a_3, \cdots, a_{n - 1} + a_n$ 的 $MEX$ 。
找到 $a$ 的最小 $score$ 如果 $a$ 可以被重排。$(0 \leq a_i \leq 2 \times 10^5)$ 。

$MEX$ 即最小排除数，即一个集合的补集的最小值。

典：$MEX$ 问题可以出得很复杂，但思维的角度通常都是从最小值考虑。

显然的 $MEX$ 贪心：
要求 $a_1+ a_2, a_2 + a_3, \cdots, a_{n - 1} + a_n$ 的 $MEX$ 最小，显然从 $0$ 开始递增考虑，构造这个数不出现。一定只需要考虑有限个数即可停止，或找到通项。

逐步分析构造法：

构造 $0$ 不出现：
- 观察到 $0$ 加上任何一个正整数都会 $> 0$ ，只需要让正整数把 $0$ 隔开即可构造 $0$ 不出现。
- 若 $cnt0 \leq \lceil \frac{n}{2} \rceil$ ，则 $MEX = 0$ 。
构造 $1$ 不出现：
- 若 $cnt0 > \lceil \frac{n}{2} \rceil$ ， $0$ 一定出现，此时需要构造 $1$ 不出现。
  - 当有正整数存在，即 $n - cnt0 > 0$ 。只要 $1$ 不和 $0$ 相邻，则加上任何一个相邻数都会 $\geq 2$ 。
    - 存在 $> 1$ 的数将所有 $1$ 和 $0$ 隔开即可构造 $1$ 不出现。 $n - cnt0 > cnt1$ ， $MEX = 1$ 。
    - 否则 $1$ 一定出现， $n - cnt0 = cnt1$ ， $MEX = 2$ 。
  - 当没有正整数存在，即 $n - cnt0 = 0$ ，则此时 $MEX = 1$ 。
当无法构造 $1$ 不出现，此时正整数都为 $1$ 且 $cnt0 > \lceil \frac{n}{2} \rceil$ ，一定可以构造 $2$ 不出现，$MEX = 2$ 。不再有其他情况。

view

#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) std::cin >> a[i];
	int cnt0 = std::count(a.begin(), a.end(), 0), cnt1 = std::count(a.begin(), a.end(), 1);;
	if (cnt0 <= (n + 1) / 2) std::cout << 0 << '\n';
	else if (cnt0 < n) {
		if (n - cnt0 > cnt1) std::cout << 1 << '\n';
		else std::cout << 2 << '\n';
	}
	else if (cnt0 == n) std::cout << 1 << '\n';
	else std::cout << 2 << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}