【反悔贪心】2022ICPC南京 G

Problem - G - Codeforces

题意

思路

首先容易发现，合并操作对平均攻击力有贡献，但是加一个1就没有贡献，因此首先考虑每次遇到0的时候都合并

但是很快发现如果这样的话，遇到-1就不一定有足够的1给你合并，因此在遇到0的时候还得考虑后面够不够

这里的做法是反悔贪心，先默认每次遇到0的时候合并，然后在遇到-1发现不够的时候反悔，把之前的合并变成加1即可

实现的话就是维护的思想，只需要维护攻击力之和 和 个数

在反悔的时候，考虑维护的东西在反悔之前和之后的差值

比如原来是 1 1

合并的时候合并成2

但是现在反悔，先加1变成1 1 1，再合并变成 1 2

这样 攻击力之和就 + 1， 个数也 + 1

Code：

#include 
 
constexpr int N = 1e6 + 10;
constexpr int mod = 998244353;
constexpr int Inf = 0x3f3f3f3f;
 
int n;
int a[N];
 
void solve() {
	std::cin >> n;
	for (int i = 1; i <= n; i ++) {
		std::cin >> a[i];
	}
	int tmp = 0, cnt = 1, w = 1;
	bool ok = true;
	for (int i = 1; i <= n; i ++) {
		if (a[i] == 1) {
			cnt ++;
			w ++;
		}else if (a[i] == -1) {
			if (cnt >= 2) {
				cnt --;
			}else {
				if (tmp == 0) ok = false;
				else {
					tmp --;
					cnt ++;
					w ++;
				}
			}
		}else {
			if (cnt == 1) {
				cnt ++;
				w ++;
			}else {
				cnt --;
				tmp ++;
			}
		}
	}
	if (ok) {
		int d = std::__gcd(w, cnt);
		w /= d;
		cnt /= d;
		std::cout << w << " " << cnt << "\n";
	}else {
		std::cout << -1 << "\n";
	}
}
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int t = 1;
	std::cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}