526互联

Codeforces Global Round 11 A. Avoiding Zero

发布时间 2023-10-13 20:18:00作者: zsxuan

给一个大小为 \(n\) 的数组 \(a_1, a_2, \cdots, a_n\) 。你需要构造一个大小为 \(n\) 的数组 \(b\) 且满足以下条件：

  • 数组 \(b\) 是数组 \(a\) 的冲排列
  • 对于 \(\forall k =1, 2, \cdots, n\) ， \(\sum_{i=1}^{k} b_i \neq 0\) 。

输出任意一组构造，或者回答不可能。

若 \(\sum_{i = 1}^{n} a_i = 0\) ， \(\sum_{i=1}^{n} b_i = 0\) 恒成立。于是无法构造 \(b\) 。

否则可以构造出一个 \(b\) 。定义 \(S_{r} = \sum_{i = 1}^{n} b_i\) ，下面给出构造性证明：

  • 若 \(\sum_{i = 1}^{n} a_i > 0\) ，让 \(b\) 为 \(a\) 的非升序排序，于是 \(S(x)\) 的图像为先非降，后非升。显然最小值为 \(S_{1}\) 或 \(S_{n}\) ，且都 \(> 0\) 。
  • 若 \(\sum_{i = 1}^{n} a_i < 0\) ，让 \(b\) 为 \(a\) 的非降序排序，于是 \(S(x)\) 的图像为先非升，后非降。显然最大值为 \(S_{1}\) 或 \(S_{n}\) ，且都 \(< 0\) 。
view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin>> n;
	std::vector<ll> a(n+1);
	ll sum = 0;
	for (int i = 1; i <= n; i++) std::cin >> a[i], sum += a[i];
	if (sum == 0) std::cout << "NO\n";
	else {
		std::cout << "YES\n";
		std::sort(a.begin() + 1, a.end());
		if (sum > 0) std::reverse(a.begin() + 1, a.end());
		for (int i = 1; i <= n; i++) std::cout << a[i] << " \n"[i==n];
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}