题目描述
链接:https://ac.nowcoder.com/acm/contest/1006/D
来源:牛客网
输入一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。
例如 1,-3,5,1,-2,3
当m=4时,S=5+1-2+3=7
当m=2或m=3时,S=5+1=6
这个题既然出现在队列的题里面了,那我们就简简单单的用一个单调队列来解决。
分析
看到区间二字,我们首先想到前缀和数组,将原序列转化为前缀和数组后,我们要求的一段序列和,也就成了前缀和数组S[i]在[l,r]上的和,即s[r]-s[l-1];
也就是说,我们要在前缀和数组上找到两个点x,y,使得s[x]-s[y]最大,并且x-y<=m。
但又有一个问题,如果我们直接暴力枚举x,y,那必然超时,这个时候队列的作用就体现了,我们可以先固定右端点i,再去寻找一个左端点j,使得s[j]值最小,并且我们还可以确定j的范围[i-m,i-1],然后自己手捏数据找规律,我们可以发现 最优决策集合一定是一个下标位置递增,对应前缀和数组值也递增的序列。
好,理论有了,动手实践。
#include<bits/stdc++.h> using namespace std; #define int long long #pragma GCC optimize(3)//手动开O3,你值得拥有 int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*f; } const int N=3e5+10; int n,m; int q[N]; int s[N]; signed main() { n=read(),m=read(); for(int i=1;i<=n;i++) { s[i]=read(); s[i]+=s[i-1];//变为前缀和 } int l=1,r=1;//队头,队尾 int ans=-0x3f3f3f3f; for(int i=1;i<=n;i++) { if(i-q[l]>m) l++;//区间长度大于m,出队 ans=max(ans,s[i]-s[q[l]]);//寻找最优解 while(l<=r&&s[q[r]]>=s[i]) r--;//如果队尾不满足单调递增,出队 q[++r]=i;//把i当成新的决策点 } cout<<ans; return 0; }