1 条题解
-
0lzxzy LV 6 MOD @ 2019-05-04 11:57:02
对于序列最值问题,一般都要记录前缀和。用\(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
信息
- ID
- 1003
- 难度
- 5
- 分类
- (无)
- 标签
- (无)
- 递交数
- 7
- 已通过
- 1
- 通过率
- 14%
- 上传者