BZOJ2288 生日礼物

题解 算法-贪心 数据结构-堆
题目链接 编辑文章

题意

在长度为 $N$ 的数列中选择不超过 $M$ 段连续的数,求这些数总和的最大值。

$N,M\le 10000$ 。

题解

可以先将连续的相同符号的数合并起来,并忽略 $0$ 。因为取正数时一定会把一整段取完,取负数也肯定会把自己这段和两边的正数段取完。

这样得到的新序列是正负交替的,下面处理新数列。

先贪心的把所有正数取完,并记正数的个数为 $cnt$ 。如果 $cnt\le m$ ,那么此时就已经得到答案;否则需要进行调整,方式有两种:

  1. 不取某个正数
  2. 将两个正数合为一段,此时需要取中间的负数。

将所有数的绝对值放入一个优先队列,每次取最小的从答案中扣除。如果选择的是正数,就相当于不取;如果是负数,就相当于取了这个负数,并把左右两个数合为一段。

其它的就和 数据备份 差不多了。用数组模拟链表进行合并即可。

但还是有区别,对于两端的数,如果是负数则不能取,因为没有两个正数能合为一段。

还需要注意合并同符号的数时,因为可能有 $0$ ,所以相乘判断符号时应该用当前的新数列而不是旧数列的上一项(见代码)

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

bool vis[100005];
priority_queue <pr,vector<pr>,greater<pr> > q;
int n,m,a[100005],s[100005],l[100005],r[100005];

inline void del(int x) //删除节点
{
    vis[x]=1;
    l[r[x]]=l[x];
    r[l[x]]=r[x];
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    int cnt=0;
    s[++cnt]=a[1];
    for (int i=2;i<=n;i++)
    {
        if (!a[i]) continue;
        if (a[i]*s[cnt]>0) s[cnt]+=a[i]; //不能用 a[i]*a[i-1] 因为可能 a[i-1]=0
        else s[++cnt]=a[i];
    }
    n=cnt;
    int ans=0; cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]>0) ans+=s[i],cnt++; //贪心取正数
        l[i]=i-1; r[i]=i+1;
        q.push(mp(abs(s[i]),i));
    }
    if (cnt<=m) return !printf("%d",ans);
    m=cnt-m; //需要操作的次数 
    while (m)
    {
        while (vis[q.top().second]) q.pop();
        int x=q.top().first,y=q.top().second; q.pop();
        if ((!l[y] || r[y]==n+1) && s[y]<0) { del(y); continue; } //两端且 <0 则跳过
        m--;
        ans-=x;
        s[y]+=s[l[y]]+s[r[y]]; //将左右两段合并
        q.emplace(mp(abs(s[y]),y));
        del(l[y]); del(r[y]);
    }
    return !printf("%d",ans);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空