Max Sum of Max-K-sub-sequence(HDU-3415)

题目描述：

Given a circle sequence A[1],A[2],A[3]……A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1]. Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K. 给定一个环，A[1],A[2],A[3],…A[n],其中A[1]的左边是A[n]. 求一个最大的连续和，长度不超过K。

输入

The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000). 第一行一个整数T，表示数据组数.不差过100 每组数据第一行两个整数N和K(1<=N<=100000 , 1<=K<=N) 接下来一行，n个整数[-1000,1000]

输出

For each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.对于每组输出，满足条件的最大连续和以及起始位置和终止位置。 如果有多个结果，输出起始位置最小的，如果还是有多组结果，输出长度最短的。

思路：

这题就是比较简单的单调队列应用，注意：以后队列的l,r初始化尽量把l定为0，r定为-1，避免不必要的错误产生。还有要注意的是，由于此题的单调性，不用考虑多种答案比较开头和长度的情况。接下来只要队列不写错就没什么问题了（这题要仔细掌握，巩固对单调队列的理解）

//代码如下
#include<cstdio>
using namespace std;
const int maxn=200005;
int n,k,T,a[maxn],q[maxn];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		a[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			a[i]+=a[i-1];
		}
		for(int i=n+1;i<n+k;i++)a[i]=a[n]+a[i-n];
		int l=0,r=0;
		int mx=-1e9;
		int ll,rr;
		for(int i=1;i<=n+k-1;i++){
			while(l<r&&a[i-1]<a[q[r-1]])r--;
			q[r++]=i-1;
			while(l<=r&&i-q[l]>k)l++;
			if(mx<a[i]-a[q[l]]){
				mx=a[i]-a[q[l]];
				ll=q[l]+1;
				if(i>n)
					rr=i%n;
				else rr=i;
			}
		}
		printf("%d %d %d\n",mx,ll,rr);
	}
	return 0;
}