题目链接:Click
here~~
上次比赛的一道题,可以用单调队列做。
题意:
给你一个n项的序列,每次可以把序列的首项移动到末尾,显然一共可以构成 n 种序列,问一共有多少种序列满足条件:序列的前 i 项和都大于等于0(i:1~n)。
解题思路:
开一个 2*n 的数组,后面 n 项复制前面 n 项。这样,每个长度为 n 的区间都代表一种序列(这也是循环序列的一般做法吧)。
然后,数组中的值 sum[i] 记录前面 i 项的和 (1 ~ i)。
这样,我们在考虑以 k 为起点的区间时,只要把 sum[i] - sum[k-1] 便可得到以 k 为起点的序列的前 j 项和(j=i-k+1)。
如果当前区间中的最小的 sum[i] 都满足 sum[i] - sum[k-1] >= 0,那么区间中的所有值也一定满足此条件。
问题从而转化成了如何求滚动区间中的最小值,我们不难想到单调队列的做法。复杂度O(n)。
#include <stdio.h> const int M = 1000002<<1; //2倍空间 int sum[M],q[M]; //sum记录前i项和,q记录队列中元素的位置 int head,rear,ans,n; void In_queue(int i) { while(head <= rear && sum[i] <= sum[ q[rear] ])//删除队中大于等于它的元素 rear--; q[++rear] = i; } void Out_queue(int i) { if(q[head] < i - n + 1) //如果队首不在区间范围内,删除 head++; } int main() { while(scanf("%d",&n),n) { ans = 0 , head = 0 , rear = -1; //初始队列指针 for(int i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i+n] = sum[i]; } for(int i=2;i < 2*n ;i++) sum[i] += sum[i-1]; for(int i=1;i < n ;i++) In_queue(i); //入队 for(int i=n;i < 2*n ;i++) //依次求区间[i-n+1,i]中的最小值 { In_queue(i); //入队 Out_queue(i); //出队 if(sum[ q[head] ] - sum[i-n] >= 0) //如果最小值都大于等于0,计数 ans++; } printf("%d\n",ans); } return 0; }