自动搬运

查看原文

来自洛谷，原作者为

	yedalong 注意力不够？刷题来凑！

搬运于2025-08-24 23:09:04，当前版本为作者最后更新于2025-01-31 20:06:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

在写这题之前，建议大家先看一下这一道题
相信大家发现此题与这一道题很像，唯一不同的就是此题加上了 $x$ 这一基准。

思路

那这一道题是怎么操作的呢？我们可以先从第一个数开始选，用一个变量存当前的和。当我们发现这个变量的值小于 $0$ 时，那还不如不选，我们就直接重新将变量赋值为 $0$ 即可。此外，还要有一个存答案的变量，在每一次存当前的和的变量值发生改变时，就更新最大值。
讲得这么清楚，这一道题的代码也就很好写了，具体如下：

#include <bits/stdc++.h>
using namespace std;
int n,x,sum,ans=-1e9;
int main(){
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>x;
		sum+=x;
		ans=max(ans,sum);
		if(sum<0) sum=0;
	}
	cout<<ans;
	return 0;
}

回归正题，我们可以将 $x$ 减去此题的数列，接着进行上述的操作，最后只需输出答案加上原数组的和即可。

AC code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,x,t,ans,now,sum;
signed main(){
    cin>>n>>x;
    for(int i = 1;i<=n;i++){
        cin>>t;
        sum+=t;
        now+=x-t;//将这个值赋值为 x 就等价于贡献了 x-t
        ans=max(ans,now);
        if(now<0) now=0;
    }
    cout<<ans+sum;
    return 0;
}