P10478 生日礼物

Genius_Star · 2024-05-16 19:14:20 · 题解

思路：

考虑贪心：

对于一段正数，一定一起被选中，可以加起来看成一个数。
对于一段负数，也一定一起被选中，因为选它是为了连续选它两端的正数，则也可以加起来看成一个数。

若最左边与最右边是负数，则不必考虑，因为肯定不会选，那么此时序列 a 肯定是下述的形式。

+-+-+\cdots +-+-+

设里面有 A 个正数：

若 M \ge A，则正数全选，忽略负数。
若 M < A，先选出所有正数，然后考虑退款。

对于第二种情况，需要进行 A-M 次退款，有两种情况可以退款：

不选某个正数。
把两个正数和中间负数一起合并。

需要注意到每次退款可能造成新的情况：

不选某个正数之后，可以与该正数两端负数合并出一个新的数，看作负数；可以用情况二加回来。
把两个正数和中间负数一起合并后，可以把他们合起来看作一个正数；可以用情况一退款。

先令 ans 为所有正数的和，先将序列中所有数加入堆中，是按照绝对值的小根堆，那么有两种情况：

若 a_x < 0，那么就相当于与两边的正数合并（因为是当前绝对值最小的，依旧是最优策略）；然后删除 x-1,x+1，将 a_{x-1} + a_{x+1} - a_x 放到 x 处。
若 a_x \ge 0，那么相当于舍弃某个正数，然后也相当于与两端的负数进行合并；然后删除 x-1,x+1，将 a_{x-1} + a_{x+1} - a_x 放到 x 处。
这里 x-1,x+1 表示的 x 上或下一个未被删除的位置，可以用双向链表维护，记录一个 l_i,r_i 即可。

因为要支持删除操作，标记一下即可，若当前堆顶已被标记，则表示被删除了，重新取出下一个堆顶，直到当前堆顶未被删除。

时间复杂度为 O(N \log N)。

完整代码：

#include<bits/stdc++.h>
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
using namespace std;
typedef long long ll;
typedef double db;
const ll N=1e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct Node{
    ll data;
    ll id;
    bool operator<(const Node&rhs)const{
        return abs(data)>abs(rhs.data);
    }
};
ll n,m,k,x,ans,cnt=1;
ll a[N],l[N],r[N];
bool f[N];
priority_queue<Node> Q;
bool check(ll x){
    if((0<l[x]&&r[x]<n+1)||a[x]>0)
      return 1;
    return 0;
}
void del(ll x){
    f[x]=1;
    l[r[x]]=l[x],r[l[x]]=r[x];
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        x=read();
        if(!x)
          continue;
        if((x>=0&&a[cnt]>=0)||(x<=0&&a[cnt]<=0))
          a[cnt]+=x;
        else
          a[++cnt]=x;
    }
    n=cnt;
    for(int i=1;i<=n;i++){
        l[i]=i-1,r[i]=i+1;
        if(a[i]>0){
            k++;
            ans+=a[i];
        }
        Q.push({a[i],i});
    }
    while(k>m){
        if(Q.empty())
          break;
        x=Q.top().id;
        Q.pop();
        if(f[x])
          continue;
        if(check(x)){
            ans-=abs(a[x]);
            a[x]+=a[l[x]]+a[r[x]];
            del(l[x]),del(r[x]);
            Q.push({a[x],x});
            k--;
        }
    }
    write(ans);
    return 0;
}