【反悔贪心】2022ICPC南京 G

港控/mmm° 2024-02-21 11:58 37阅读 0赞

[Problem - G - Codeforces][]

题意

![d90998478af246c99ef1811cc2a9b959.png][]

思路

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

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

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

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

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

比如原来是 1 1

合并的时候合并成2

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

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

Code：

#include <bits/stdc++.h>
    
    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;
    }

[Problem - G - Codeforces]: https://codeforces.com/gym/104128/problem/G
[d90998478af246c99ef1811cc2a9b959.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/ee03da39a4544df4b0d8a6943a6f4d51.png