1 条题解
-
0Guest LV 0 MOD
-
0
我,一个外人,来发一发题解。先安利一下我的luogu账号:⚡LZSY01_XZY⚡。
回到正题:
对于序列最值问题,一般都要记录前缀和。用\(sum_i\)表示\(a_1,a_2,a_3,...,a_i\)的和。
这一题要求选的序列长度大于\(a\),小于\(b\)。我们可以维护一个单调队列,记录\(i-x\)~\(i-y\)的\(sum\)的最小值。为什么是最小值呢?因为用前缀和求序列\(x\)~\(y\)的和时,式子是这样的:ans=sum[x]-sum[y-1];
我们通过枚举\(x\),再用单调队列维护\(sum[y]\)便可以求出解。
\(code:\)#include <cstdio> #include <queue> using namespace std; int read() { int 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; } const int MAXN=500005; int n,x,y,ans=-99999999; int a[MAXN],sum[MAXN]; deque<int> Q; int main() { n=read();x=read();y=read(); for (int i=1;i<=n;i++) sum[i]=sum[i-1]+(a[i]=read()); for (int i=x;i<=n;i++) { while (!Q.empty()&&sum[i-x]<sum[Q.back()])Q.pop_back(); Q.push_back(i-x); while (!Q.empty()&&i-Q.front()>y)Q.pop_front(); ans=max(ans,sum[i]-sum[Q.front()]); } printf("%d\n",ans); return 0; }
后记
自己认为此题还是比较简单的,核心就是单调队列。
其实,我真的想加入这个域。不知出题人允不允许。我的代码似乎比出题人还快!
- 1
信息
- 难度
- 4
- 分类
- (无)
- 标签
- 递交数
- 9
- 已通过
- 3
- 通过率
- 33%
- 被复制
- 1
- 上传者