自动搬运

查看原文

来自洛谷，原作者为

	Genius_Star 跟你爆了

搬运于2025-08-24 22:58:21，当前版本为作者最后更新于2024-05-16 19:14:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

考虑贪心：

• 对于一段正数，一定一起被选中，可以加起来看成一个数。

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

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

设里面有 $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;
}