* Codeforces Round 890 (Div. 2) supported by Constructor Institute B. Good Arrays

zsxuan / 2023-09-05 / 原文

————哪有岁月安好，只是有人为你负重前行

给一个长为 $n$ 的数组 $a$ ，称一个数组 $b$ 是 $good$ 的如果满足以下条件：

$\forall i, a_i \neq b_i$
$\sum_{i=1}^{n}a_i=\sum_{i=1}^{n}b_i$

判断对于一个 $a$ ，是否存在一个 $b$ 为 $good$ 。

这题思维量并不低。虽然是个 $900$ 题，但答案很容易枚举出来，基本大家 $WA$ 几发硬猜的。

观察一： $a$ $b$ 的和相等，则某个 $b$ 可以由 $a$ 构造。
观察二：$a$ 的和固定，当一个 $a_i$ 增加 $\delta x$ ，存在一个 $a_i$ 至少减少 $\delta x$ 。——哪有岁月安好，只是有人为你负重前行。
观察三：当 $n = 1$ ，没有兄弟为它负重前行。
观察四：有些兄弟完全负重不了一点，即 $1$ 。主要观察一。
观察五：有人拿了好处就会有人负重，我们不希望存有兄弟被压垮，让负重不了一点的兄弟拿最少的好处即可。
观察六：所有人的都要么得拿好处，要么得负重。产生最少的好处可能导致有人不负重。
观察七：最后不负重的人，至少可以分出随意一些好处。又拿好处不存在上限，让他们分给随意的已确定会拿到好处的人即可。不影响结果。主要观察二。

于是问题轻易可以解决：

$n = 1$ 时，没兄弟负重。此处无解。
$n > 1$ ，有好兄弟了。给所有负重不了一点的兄弟赏尽可能少的好的。查找这部分贡献能否被另外一部分兄弟均摊负重。
- 统计出 $1$ 的数量为 $cnt$ ，$a$ 的和为 $sum$ 。剩下 $n - cnt$ 个兄弟共 $sum - cnt$ 的承受力在承受 $cnt$ 的负重后不能垮，即 $(sum - cnt) - 1 \times cnt \geq 1 \times (n - cnt)$ 。则 $sum - cnt \geq n$ 时有解。

#include <bits/stdc++.h>
typedef long long ll;
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	ll sum = 0;
	int cnt0 = 0;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		sum += a[i];
		cnt0 += (a[i] == 1);
	}
	if (n == 1) std::cout << "NO" << '\n';
	else {
		// sum - cnt0 - cnt0 >= n - cnt0
		std::cout << (sum- cnt0 >= n ? "YES" : "NO") << '\n'; 
	}
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}