本题是数据备份的进阶版。
首先去掉所有0，把连续的正数/负数连起来。
计算所有正数段的个数与总和。
然后考虑数据备份，有一点区别：
如果我们在数列中选出一个负数，相当于把它左右连起来。
选出一个正数，相当于抛弃它。
总和加上那个负数/减去那个正数即为变化。
所以把val按照绝对值进堆，出来，减去绝对值即可。
注意：两边的负数不能选，因为旁边没有东西去给你连。
实际操作的时候我存了负数，在比较函数里加abs
#include <cstdio>
#include <queue>
#include <cmath>
const int N = ; struct Sta {
int p, val;
Sta(int pq, int v) {
p = pq;
val = v;
}
};
inline int abs(const int &x) {
return x > ? x : -x;
}
inline bool operator <(const Sta &x, const Sta &y) {
return abs(x.val) > abs(y.val);
}
struct ListNode {
int pre, nex, val;
bool use;
}li[N << ]; int top, head, tail; int a[N], ans, cnt;
std::priority_queue<Sta> Q; inline void init() {
head = (N << ) - ;
tail = head - ;
li[head].nex = tail;
li[tail].pre = head;
return;
} inline void add(int x) {
top++;
int p = li[tail].pre;
li[top].pre = p;
li[top].nex = tail;
li[p].nex = top;
li[tail].pre = top;
li[top].val = x;
Q.push(Sta(top, x));
if(x > ) {
ans += x;
cnt++;
}
return;
} inline int get() {
Sta t = Q.top();
Q.pop();
while(!Q.empty() && (li[t.p].use || li[t.p].val != t.val)) {
t = Q.top();
Q.pop();
}
int x = t.p; if(li[x].val < && li[x].pre == head) {
li[x].use = ;
li[li[x].nex].pre = head;
li[head].nex = li[x].nex;
return get();
}
if(li[x].val < && li[x].nex == tail) {
li[x].use = ;
li[tail].pre = li[x].pre;
li[li[x].pre].nex = tail;
return get();
} if(li[x].nex == tail && li[x].pre == head) {
li[x].use = ;
return li[x].val;
}
if(li[x].nex == tail) {
int ans = li[x].val;
li[x].val += li[li[x].pre].val;
li[li[x].pre].use = ;
li[x].pre = li[li[x].pre].pre;
li[li[x].pre].nex = x;
Q.push(Sta(x, li[x].val));
return ans;
}
if(li[x].pre == head) {
int ans = li[x].val;
li[x].val += li[li[x].nex].val;
li[li[x].nex].use = ;
li[x].nex = li[li[x].nex].nex;
li[li[x].nex].pre = x;
Q.push(Sta(x, li[x].val));
return ans;
}
int ans = li[x].val;
li[x].val += li[li[x].nex].val;
li[x].val += li[li[x].pre].val;
li[li[x].pre].use = ;
li[li[x].nex].use = ;
li[x].pre = li[li[x].pre].pre;
li[x].nex = li[li[x].nex].nex;
li[li[x].pre].nex = x;
li[li[x].nex].pre = x;
Q.push(Sta(x, li[x].val));
return ans;
} int main() {
int m, n;
init();
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
int t = ;
bool f = ;
for(int i = ; i <= n; i++) {
if(!a[i]) {
continue;
}
if(f) {
if(a[i] < ) {
continue;
}
else {
f = ;
}
}
if(1ll * a[i] * t >= ) {
t += a[i];
}
else {
add(t);
t = a[i];
}
}
if(t > ) {
add(t);
} for(int i = m + ; i <= cnt; i++) {
ans -= abs(get());
}
printf("%d", ans);
return ;
}
AC代码