codeforeces1748C Zero-Sum Prefixes（贪心）

题目链接：codeforeces 1748C

题目思路：

首先，不难想到修改的次数要最少；其次，对于一次修改，影响的是前缀和的后缀。因此，根据贪心思想，可以找原数组非零段，用它前面的0修改成这段前缀和的值出现次数最多的那个数的相反数即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;


void solve() {
   
	int n;
	cin >> n;
	vector<i64> a(n), pre(n+1);
	for (int i = 0; i < n; i++) {
   
		cin >> a[i];
		pre[i+1] = pre[i] + a[i];
	}

	int ans = 0;
	map<i64, int> cnt;
	int p = 0;
	while (p < n && a[p] != 0) {
   
		p++;
		if (pre[p] == 0) ans++;	
	}

	while (p < n) {
   
		int q = p + 1;
		while (a[q] != 0 && q < n) q++;
		for (int i = p+1; i <= q; i++) {
   
			cnt[pre[i]]++;
		}
		int mx = 0;
		for (auto [u, v] : cnt) mx = max(v, mx);
		ans += mx;
		p = q;
		cnt.clear();
	}

	cout << ans << '\n';

}

int main() {
   
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int t;
  cin >> t;
  while (t--) {
   
  	solve();
  }
  
  return 0;
}