1 条题解

  • 0
    @ 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%
上传者