题解：CF332B Maximum Absurdity

CF332B
CF332B

暴力思路

题目要我们找两个不重叠的区间，并使区间的值最大。那我们可以考虑使用双重循环搭配前缀和暴力求最大值。代码如下。

for(int i=1;i<=n;i++)
{ll l=sum[i+k-1]-sum[i-1],maxx;for(int j=i+k;j<=n;j++){maxx=l+sum[j+k-1]-sum[j-1];if(maxx>ans.sum){ans.x=i;ans.y=j;ans.sum=maxx;}}
}

但是暴力的时间复杂度是一定会超时的。那我们考虑一下优化。

优化思路

我们可以思考一下如何把第二层循环给优化掉。我们可以用一个结构体数组 $maxx[i]$ 来记录 $i\sim n$ 的最大的区间值，并记录这个区间的起点。这样我们就把第二层循环给优化掉了。

最重要的注意数据范围，要开 long long。

代码

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll unsigned long long
#define lhs printf("\n");
using namespace std;
const int N=3e5+10;
const int M=2024;
const int inf=0x3f3f3f3f;
ll n,k;
ll a[N]; 
ll sum[N];
struct node
{ll num;int id;
}maxx[N];
struct nodee
{ll sum;ll x,y;
}ans;
int main()
{scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];//前缀和} for(int i=n;i>=1;i--){if(i+k-1>n)continue;ll l=sum[i+k-1]-sum[i-1];//更新最大值if(maxx[i+1].num>l){maxx[i].num=maxx[i+1].num;maxx[i].id=maxx[i+1].id;}else{maxx[i].num=l;maxx[i].id=i;}} for(int i=1;i<=n;i++){if(i+k-1>n)continue;ll l=sum[i+k-1]-sum[i-1];ll r=maxx[i+k].num,rid=maxx[i+k].id;if(l+r>ans.sum){ans.x=i;ans.y=rid;ans.sum=r+l;}} printf("%lld %lld",ans.x,ans.y);return 0;
}