题解 The Human Equation

The Human Equation

思维题。

我们考虑每次 \(a\) 数组加一减一对于其前缀和 \(sum\) 的影响。

可以发现，假设相邻两次加一和减一的位置分别为 \(l\) 和 \(r\)，那么 \(sum\) 在 \([l,r)\) 内会加一。

先减后加也同理。

所以，一次加减操作相当于将 \(sum\) 若干段连续序列加一或减一。

而 \(sum\) 全部为 \(0\) 是 \(a\) 都变为 \(0\) 的充要条件。

因此我们只需要计算出 \(sum\) 归零的最小操作数，也就是 \(maxn-minn\)，其中 \(maxn\) 为最大正数，\(minn\) 为最小的负数。

复杂度 \(O(n)\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n; 
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> n;
		ll sum = 0, minn = 0, maxn = 0;
		for (int i = 1; i <= n; ++i) {
			ll x; cin >> x; sum += x;
			minn = min(minn, sum);
			maxn = max(maxn, sum);
		}
		cout << maxn - minn << endl;
	}
	return 0;
}