题目
给你长度为 $n$ 的序列，你有一种能力可以将序列中的任意一个数变为相反数，在你不超过 $k$ 次使用能力的情况下，长度为 $len$ 的子区间的和的绝对值的最大值是多少？
Solution
用两个multiset维护区间前k大的负数，扫一遍就好了，细节略多。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, len, k;
ll x1, x2, a[200005];
ll solve() {
ll sum = 0, ma = -1e18;
multiset<ll> s1, s2;
for (int i = 1; i <= n; i++) {
if (a[i] >= 0)
sum += a[i];
else if (s1.size() < k) {
s1.insert(a[i]);
sum -= a[i];
} else if (k && a[i] < *(--s1.end())) {
ll x = *(--s1.end());
sum += 2 * x;
s1.erase(--s1.end());
s2.insert(x);
s1.insert(a[i]);
sum -= a[i];
} else {
s2.insert(a[i]);
sum += a[i];
}
int j = i - len;
if (j > 0) {
if (a[j] >= 0)
sum -= a[j];
else if (s1.find(a[j]) != s1.end()) {
s1.erase(s1.find(a[j]));
sum += a[j];
if (s2.size() > 0) {
ll x = *(s2.begin());
s1.insert(x);
s2.erase(s2.begin());
sum -= 2 * x;
}
} else {
s2.erase(s2.find(a[j]));
sum -= a[j];
}
}
if (j >= 0) ma = max(ma, sum);
}
return ma;
}
int main() {
scanf("%d%d", &n, &len);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
scanf("%d", &k);
x1 = solve();
for (int i = 1; i <= n; i++) a[i] = -a[i];
x2 = solve();
printf("%lld\n", max(x1, x2));
return 0;
}
|