526互联

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

发布时间 2023-09-05 21:22:53作者: zsxuan

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

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

  1. \(\forall i, a_i \neq b_i\)
  2. \(\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\) 。主要观察一。
观察五：有人拿了好处就会有人负重，我们不希望存有兄弟被压垮，让负重不了一点的兄弟拿最少的好处即可。
观察六：所有人的都要么得拿好处，要么得负重。产生最少的好处可能导致有人不负重。
观察七：最后不负重的人，至少可以分出随意一些好处。又拿好处不存在上限，让他们分给随意的已确定会拿到好处的人即可。不影响结果。主要观察二。

于是问题轻易可以解决：

  1. \(n = 1\) 时，没兄弟负重。此处无解。
  2. \(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;
}