HDU 3415 Max Sum of Max-K-sub-sequence（单调队列）

Given a circle sequence A 1 1,A 2 2,A 3 3......A n n. Circle sequence means the left neighbour of A 1 1 is A n n , and the right neighbour of A n n is A 1 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. Input 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). Output 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. Sample Input 4 6 3 6 -1 2 -6 5 -5 6 4 6 -1 2 -6 5 -5 6 3 -1 2 -6 5 -5 6 6 6 -1 -1 -1 -1 -1 -1

   【题意】一个长度为n的循环序列，在其中找一个长度为k(k<=n)的子序列，要求这个子序列的和尽可能大，最后输出最大值，并且输出子序列的起点和终点。

   【分析】先用sum数组来保存前i个数的和，记得还要保存i到n+k的数的和，因为这是要构成首尾相连。然后从头开始，找子序列的最大值，双端单调队列队首永远是序列和最大的，往后依次递减，每移动一次保存一下和前一次ans的最小值，最后输出。

   【用时】452 ms！！

   【AC代码】

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=2e5+10; const int INF=1e7; int a[N],sum[N]; int head; int tail; int str[N]; int n,nn,k,maxn; int s,e; int min(int x,int y) { return x>y?y:x; } void push_up(int i) { str[tail++]=i; } bool isempty() { return head==tail; } int Front() { return str[head]; } void Pop_back() { tail--; } void Pop_front() { head++; } void solve() { head=tail=0; int i; for(i=1;i<=n;i++) { while(!isempty() && sum[i-1]<sum[str[tail-1]]) Pop_back(); while(!isempty() && str[head]+k<i) Pop_front(); push_up(i-1); if(sum[i]-sum[str[head]]>maxn) { maxn = sum[i]-sum[str[head]]; s = str[head]+1; e= i ; } } if(e>nn) e%=nn; printf("%d %d %d\n",maxn,s,e); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); nn=n; int i; for(i=1,sum[0]=0;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } for(;i<n+k;i++) sum[i]=sum[i-1]+a[i-n]; n=n+k-1; maxn=-INF; solve(); } return 0; }