题解：P11642 【MX-X8-T1】「TAOI-3」幸运草

yedalong · 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;
}