<题目链接>
题目大意：
给你一段从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=2*100000+5; #define INF 1e9 int a[M],q[M]; int main(){ int _;scanf("%d",&_); while(_--){ int n,k; 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++){ //将这个序列补到n+k-1,因为每个位置作为单调序列的头节点的情况都要考虑 a[i]=a[n]+a[i-n]; } int mx=-INF,st,et; int head=0,tail=0; for(int i=1;i<=n+k-1;i++){ while(head<tail&&a[i-1]<a[q[tail-1]])//tail-1才是尾节点的位置，tail为代插入节点的位置,该优先队列维护的是前缀和的最小值，是一个关于前缀和的单调递增序列,然后根据为尾节点-头节点 --tail; q[tail++]=i-1; //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]+1; et=i>n?i%n:i; } } printf("%d %d %d ",mx,st,et); } return 0; }
2018-09-23