学步园

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=3415

给你一个可循环的数列，1——n

然后给你一个数字k

‘要你求出长度不大于k的最大子串和

我们用sum数字求出1~i的连续和

然后对于j，我们只需要找到一个i，i>=j-k+1，且sum[i-1]最小

那么对于j来说，这个就是我们可以求出来的最大子串和

然后用过o(n)求出答案

但是对于每个j，都会有很多不同的i，我们就要用单调队列来维护

即要找到符合条件的最小的sum[i-1],即i-1>=j-k，因为对于每个j来说

求子串和使用s[j]-s[j-1]来求i~j的子串和的

弄清楚了题意，解题就很方便了

直接用deque来实现单调队列

对于每一个j-1，如果它当前比队尾还小，则不停的删除，直到可以插入

然后还要检查头部

如果当前的头部，即q.front()如过小于j-k(j是我们当前的尾部)，那么就删除头部

这样一来，就使头部就是我们要的那个i，然后就比较已知的ans，进行选择

下面上代码：

#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;

const int maxn = 100000+20;
int sum[maxn*2];
int a[maxn*2];
int t,n,k;
deque<int> q;


int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&k);
        sum[0]=0;
        int tmp;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[n+i]=a[i];
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=n+1;i<=n+k;i++)
        {
            sum[i]=sum[i-1]+a[i];
        }
        q.clear();
        int ans = -0x3f3f3f3f;
        int s,e;
        for(int i=1;i<=n+k;i++)
        {
            while(!q.empty() && sum[i-1]<sum[q.back()])
                q.pop_back();
            q.push_back(i-1);
            while(q.front()<i-k)
                q.pop_front();
            if(sum[i]-sum[q.front()] > ans)
            {
                ans=sum[i]-sum[q.front()];
                s=q.front()+1;
                e=i;
            }
        }
        printf("%d %d %d\n",ans,s,e>n?e%n:e);
    }
    return 0;
}