WA#53 第49个点求助
查看原帖
WA#53 第49个点求助
362750
TernaryTree楼主2023/7/4 11:13
#include <bits/stdc++.h>
#define int long long 

using namespace std;

const int maxn = 1e6 + 10;

int t, n, p, q;
int a[maxn];
int b[maxn];

signed main() {
	cin >> t;
	while (t--) {
		cin >> n, p = q = 0;
		for (int i = 1; i <= n; i++) cin >> a[i], (i & 1 ? p : q) += a[i];
		for (int i = 1; i <= n; i++) if (a[i - 1] + a[i + 1] < a[i]) b[i] = 1;
		for (int i = 1; i <= n; i++) b[i] += b[i - 1];
		if (p == q && !b[n]) {
			puts("YES");
			continue;
		}
		bool f = false;
		for (int i = 1; i < n; i++) {
			int x = (i & 1 ? p : q) + a[i + 1] - a[i];
			int y = (i & 1 ? q : p) - a[i + 1] + a[i];
			swap(a[i], a[i + 1]);
			if (x == y) {
				bool flag = true;
				for (int j = max(1ll, i - 1); j <= min(n, i + 2); j++) {
					if (a[j - 1] + a[j + 1] < a[j]) {
						flag = false;
						break;
					}
				}
				if (flag && !(b[max(0ll, i - 2)] + b[n] - b[min(n, i + 2)])) {
					f = true;
					break;
				}
			}
			swap(a[i], a[i + 1]);
		}
		puts(f ? "YES" : "NO");
		for (int i = 1; i <= n; i++) a[i] = b[i] = 0;
	}
	return 0;
}

2023/7/4 11:13
加载中...