<题目链接>
题目大意：
给你一段从1~N的圆形序列，要你求出这段圆形序列中长度不超过K的最大连续子序列之和是多少，并且输出这子序列的起点和终点。
解题分析：
既然是求连续子序列之和，我们不妨将这段序列的前缀和算出来。因为本题规定了序列的最长长度，很容易想到单调队列，我们可以用一个单调队列去维护前缀和的最小值，让每一次移动的最小的前缀和都为单调队列的队首，也就是该单调队列为单调递增的序列。对于新访问的点，如果它的前缀和小于队列的尾端，那么删除队列的尾端，将其插入队列的合适位置，维护队列的递增性。如果遍历到的点的下标与队列头节点下标之差>K，说明队列维护的连续序列的长度不符合题目要求，将队列头结点删除。最终，每一次遍历，队列的头结点的下标到 i (i此时为队列的尾节点下标) 为每一次的最大连续和的序列(因为队列的头结点始终维护的是在指定区间内最小的前缀和)。需要注意的是，假如 队列记录的是 a~ i 这段连续子序列，那么只需要记录 a-1 就够了，因为[a,i]这段序的和为 sum[i]-sum[a-1]，方便计算。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int M=*+;
#define INF 1e9
int a[M],q[M]; int main(){
int _;scanf("%d",&_);
while(_--){
int n,k;
scanf("%d %d",&n,&k);
a[]=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
a[i]+=a[i-];
}
for(int i=n+;i<n+k;i++){ //将这个序列补到n+k-1,因为每个位置作为单调序列的头节点的情况都要考虑
a[i]=a[n]+a[i-n];
}
int mx=-INF,st,et;
int head=,tail=;
for(int i=;i<=n+k-;i++){
while(head<tail&&a[i-]<a[q[tail-]])//tail-1才是尾节点的位置，tail为代插入节点的位置,该优先队列维护的是前缀和的最小值，是一个关于前缀和的单调递增序列,然后根据为尾节点-头节点
--tail;
q[tail++]=i-; //q[]数组记下i-1的下标，方便求前缀和的时候做差
while(head<tail&&i-q[head]>k) //如果队首坐标与队尾坐标相差大于k，则将队首删除
++head;
if(mx<a[i]-a[q[head]]){ //如果单调队列维护的这个区间和大于当前最大值
mx=a[i]-a[q[head]];
st=q[head]+;
et=i>n?i%n:i;
}
}
printf("%d %d %d\n",mx,st,et);
}
return ;
}
2018-09-23