题解：P10478 生日礼物

luxiaomao · 2024-06-21 17:22:39 · 题解

P10478 反悔贪心经典例题

刚写完，想去冲双倍经验 P6821 结果被加强数据硬控，所以来写篇题解涨一涨 RP。

upd：代码过不了样例，已修改，望通过。

Solution

题意不难理解。

首先可以发现，如果没有 m 这个限制（或者说 m 足够大），那么我们的答案就是序列中所有正数的和。

那么我们可以先求出这样情况下的正区间个数 cnt，然后再把这个 cnt 逐步降到 m。

怎么降？有两种方式：

• 抛弃一个正区间，这能让 cnt 减掉一。

• 选择一个负区间算入答案，这能让它左右两个正区间合为一，同样使 cnt 减掉一。

那么可以发现，要求这些被抛弃掉的贡献，实质就是求从若干个正负区间中选择互不相邻的 (cnt-m) 个区间，使这些区间的绝对值之和最小。

把区间视作点，那么这道题就被完美转化成了 P1484，即反悔贪心的模板。

笔者采用优先队列 + 链表来实现。

Code

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;

int n,m,a[N];
int b[N],tot,ans;

int l[N],r[N];
bool flag[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i = 1;i <= n;i++)
        scanf("%lld",&a[i]);
    int cnt = 0;
    for(int i = 1;i <= n;i++)
    {
        if(a[i] * b[tot] < 0)
            b[++tot] = a[i];
        else 
            b[tot] += a[i];
    }
    if(b[tot] < 0)tot--;
    for(int i = 1;i <= tot;i++)
    { 
        if(b[i] > 0)cnt++,ans += b[i];
        l[i] = i-1,r[i] = i+1;
        q.push(make_pair(abs(b[i]),i)); 
    } 
    r[0] = 1,l[tot+1] = tot;
    b[0] = b[tot+1] = 1e10;
    while(cnt > m)
    {
        while(flag[q.top().second])q.pop();
        int u = q.top().second;q.pop();
        if((l[u]==0 || r[u]==tot+1) && b[u] < 0)continue;
        cnt--,ans -= abs(b[u]);
        b[u] += b[l[u]]+b[r[u]],q.push(make_pair(abs(b[u]),u));
        flag[l[u]] = flag[r[u]] = 1;
        l[u] = l[l[u]],r[u] = r[r[u]];
        r[l[u]] = u,l[r[u]] = u;
    }
    printf("%lld\n",ans);
    return 0;
}