题目链接:Click
here~~
前几天学的单调队列,然后找题目练习,看这道题两天了,终于想通了。
题意:
给你一个循环序列{An},让你找出长度不大于K的连续子序列,使这个子序列和最大。
解题思路:
由于子序列连续,所以和上道题目一样,它的和可以通过两个前缀和作差得到。(即sum[i~j]=sum[j]-sum[i-1](j-i+1<=k))
而对于同一个序列终点来说,起点左边那个元素的前缀和越小,所得到的和越大。
所以,题目又变成了求滚动区间的最小值问题。
#include <stdio.h> #include <limits.h> const int M = 100001<<1; int sum[M],q[M]; int main() { int z,n,k; scanf("%d",&z); while(z--) { int start,end,max; int head,rear; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i+n] = sum[i]; } for(int i=2;i< n+k;i++) sum[i] += sum[i-1]; head = rear = 0; q[head] = 0; max = INT_MIN; for(int i=1;i< n+k;i++) //枚举每个区间终点 { while(head<=rear && sum[i-1]<=sum[ q[rear] ]) rear--; q[++rear] = i-1; if(q[head]+1 < i-k+1) //起点如果大于区间范围,删除队首 head++; if(sum[i] - sum[ q[head] ] > max) { start = q[head]+1; end = i; max = sum[i] - sum[ q[head] ]; } } end = end>n ? end%n : end; printf("%d %d %d\n",max,start,end); } return 0; }