hdu 3415 Max Sum of Max-K-sub-sequence【单调队列】

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100000+10;
int sum[maxn<<1],que[maxn<<1];
void read(int &d)
{
    char ch;bool flag=0;
    while(ch=getchar(),(ch>'9'||ch<'0')&&ch!='-');
    ch=='-'?d=0,flag=1:d=ch-48;
    while(ch=getchar(),ch<='9'&&ch>='0') d=d*10+ch-48;
    if(flag) d=-d;
}
int main()
{
    int t,n,k;
    read(t);
    while(t--)
    {
        read(n),read(k);
        for(int i=1;i<=n;i++) read(sum[i]),sum[i]+=sum[i-1];
        for(int i=n+1;i<n+k;i++) sum[i]=sum[n]+sum[i-n];
        int head=0,rear=-1,maxs=1<<31,start,end;
        for(int i=1;i<n+k;i++)
        {
            while(head<=rear&&sum[que[rear]-1]>sum[i-1]) rear--;
            que[++rear]=i;
            while(que[rear]-que[head]>=k) head++;
            if(sum[i]-sum[que[head]-1]>maxs)
                maxs=sum[i]-sum[que[head]-1],start=que[head],end=i>n?i-n:i;
        }
        printf("%d %d %d\n",maxs,start,end);
    }
    return 0;
}