题目传送门
题意
给定一个长度为 $n$ 的数组 $a$。每次操作，你可以选出 $a$ 的一个子序列 $b$ ，然后将 $b$ 中奇数位+1，偶数位-1；或者奇数位-1，偶数位+1。求最少多少次操作能使所有数变成 $0$。
$n \le 2\cdot 10^5$
题解
发现如果有相邻的两个数 $x,y$ 正负性相同，那么将它们合并为 $x+y$ 是不影响的。
根据这个，我们先把 $a$ 中能合并的都合并了，合并之后，$a$ 中任意相邻两个数正负性都不同。
显然，我们不会把一个正数+1，或者把一个负数-1。所以每次操作一定是把每个正数-1，每个负数+1（因为现在的数组是奇偶相间的）。
当数组中一个数被加/减到 0 的时候，我们将其从数组中删去，同时合并它的左右两个数（这两个数正负性一定相同）。直到数组被清空为止。我们用链表来维护数组，multiset 维护最小值，同时维护现在的时刻。数组清空时的时刻就是答案。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| ll n, a, ans;
vector<ll>v;
int l[200005], r[200005];
multiset<pair<ll, int>>s;
void solve() {
cin >> n;
v.clear();
ans = 0;
rep(i, n) {
cin >> a;
if (!a)continue;
if (v.empty() || (v.back() > 0 && a < 0) || (v.back() < 0 && a > 0))v.pb(a);
else v.back() += a;
}
n = v.size();
rep(i, n) {
if (i)l[i] = i - 1;
else l[i] = n;
if (i < n - 1)r[i] = i + 1;
else r[i] = n;
}
rep(i, n)v[i] = abs(v[i]), s.insert(mp(v[i], i));
while (!s.empty()) {
auto it = s.begin();
int x = (*it).se;
ans = v[x];
r[l[x]] = r[x], l[r[x]] = l[x];
s.erase(it);
if (l[x] != n && r[x] != n) {
int L = l[x], R = r[x];
s.erase(mp(v[L], L)), s.erase(mp(v[R], R));
v[L] += v[R] - ans;
r[L] = r[R], l[r[R]] = L;
s.insert(mp(v[L], L));
}
}
cout << ans << endl;
}
|