P10478 生日礼物

洛谷题目链接。

调了好久。。

思路

贪心。

显然对于一段连续的正数，都选是最优的。而一段连续的负数，如果想要将两端正数和这一段负数连成一整段，使选的段数减少 1，这一段负数不妨累和看成一个负数。

预处理合并都是正数的子段和都是负数的子段，于是成了一个正负数交替出现的数列。

如果正数的个数小于等于 m，代表全都能选上，直接输出并结束即可。再选负数就不优了。

数列的第一个数是负数不选，最后一个数是负数也不选。因为选了只会减少答案，而不能使答案更优。

于是剩下一个首尾都是正数、正负数交替出现的数列。

对于一个正数：

• 不选，删掉。
• 选。

对于一个负数：

• 选，连上两边正数，三个数并成一个新的正数。
• 不选。

那么对于一个不选的正数，可以完全不理这个数，还可以和两边负数一起并成一个新的负数。后者更优，因为完全不理这个数的话，需要在这个数的两边选，但是可能覆盖到这个数选会更优，当然并起来之后也可以不选这个数。为了避免分类讨论就把他并起来。

现在正数和负数的情况基本统一了，我们需要考虑的问题是要选哪些数并起来更优。

对于一个要合并的负数，显然这个数的数值越大，花费越小，答案越优。

对于一个要合并的正数，显然这个数的数值越小，损耗越小，答案越优。

于是可以得出按照绝对值排序最优。由于不论是花费还是损耗都是减少答案，所以需要正负数一起考虑，把数列按照绝对值排序塞到一个堆里。

上述合并需要快速查询到一个数相邻的数，还需要删除一个数，可以手写链表，也可以并查集实现。代码给出的是手写链表。

答案统计的话，由于不论是正负数都是减小答案，所以在删数之前把所有正数累和，合并的过程中减去当前数的绝对值就好了。

注意链表实现的细节，链表头之前与链表尾之后的数需要设成无穷大，避免意外入堆。遇到表头或表尾为负数要跳掉。因为有删除操作，需要记录当前数有没有被删除。注意 m 可能为 0。

有其他情况过不了的话可以看讨论区中的 hack 或是自己对拍。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1000010
int n, m, tot = 1, ls[N], rs[N];
bool vis[N];
ll a[N], ans, b[N];
#define PLL pair < ll, int >
#define fi first
#define se second
priority_queue < PLL, vector < PLL >, greater < PLL > > q;
int main() {
    scanf("%d %d", &n, &m);
    bool fl = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", a + i);
        if (a[i] > 0) fl = 0;
    }
    if (fl) return puts("0"), 0; // 可以一个也不选
    ll sum = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0) continue; // 注意 0！！
        if (a[i] < 0) {
            if (b[tot] > 0) ++tot;
        } else {
            if (b[tot] < 0) ++tot;
        }
        b[tot] += a[i];
    }
// 预处理数列
    for (int i = 1; i <= tot; ++i) 
        if (b[i] > 0) ++cnt, sum += b[i]; // 正数累和，cnt 表示正数个数
    if (cnt <= m) return printf("%lld", sum), 0;

    if (b[1] <= 0) {
        for (int i = 1; i < tot; ++i) b[i] = b[i + 1];
        --tot;
    }
    if (b[tot] <= 0) --tot; // 过滤第一个数和最后一个数是负数的情况，也可以再后面判断

    for (int i = 2; i < tot; ++i) ls[i] = i - 1, rs[i] = i + 1;
    rs[1] = 2, ls[tot] = tot - 1;
    rs[0] = 1, ls[tot + 1] = tot; 
    ls[0] = 0, rs[tot] = tot + 1;
// ls 表示左边的数 rs 表示右边的数
    b[0] = b[tot + 1] = 2147483647; 
    for (int i = 1; i <= tot; ++i) q.push({ abs(b[i]), i })/*, cout << b[i] << " " << i << endl*/;
    while (cnt > m) {
        PLL tmp = q.top();
        q.pop();
        int x = tmp.se;
        if (vis[x]) continue;
        int l = ls[x], r = rs[x];
        if ((l <= 0 || r <= 0 || r >= tot + 1) && b[x] <= 0) continue;
        --cnt;
        b[x] += b[l] + b[r]; // 合并
        vis[l] = vis[r] = 1;
        ls[x] = ls[l], rs[x] = rs[r];
        rs[ls[l]] = x, ls[rs[r]] = x;
        sum -= tmp.fi;
        q.push({ abs(b[x]), x });
    }
    printf("%lld", m ? sum : 0); // 注意 m 可能为 0
    return 0;
} 

祝大家 NOIP RP++！