!HDU 4193 循环序列前缀和非负-单调队列-(区间最值)

时间:2021-03-13 17:39:19

题意:一个数列,求分别以每个元素为首位时(循环),前缀和都非负的序列个数

分析:

首先是个循环序列问题,所以要做处理:把序列复制一遍变成2*n的序列,这样任意一个长度为n的区间就是一种序列,共n种

然后求前缀和就可以用sum[j]-sum[i-1],这个式子表示以第i的元素为首位的序列,然后以第j个元素结尾的前缀和。同一个序列的不同结尾的前缀和每次都是减sum[i-1],只有sum[j]不同,所以我们就求出sum[j]中最小的再减去sum[i-1]看是否小于0即可。sum[]很好求,O(2*n)就求出来了,因此我们现在就是要求一个长度为n的区间里面sum[j]的最小值,也就是一个移动的固定区间求最值,用单调队列O(n)解决。

另外cin,cout又TLE了,弃用....

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int head,rear;
int a[2000010];
int q[1000010];
int n;
void pushq(int i)
{
	while(head<=rear&&a[q[rear]]>=a[i]) rear--;
    q[++rear]=i;
}
void popq(int i)
{
	while(q[head]<i-n+1) head++;
}
int main()
{
	while(scanf("%d",&n)!=EOF){
		if(!n) break;
		head=0,rear=-1;
		a[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			a[i+n]=a[i];
		}
		int tot=0;
		for(int i=1;i<=2*n;i++) a[i]+=a[i-1];
		for(int i=1;i<n;i++) pushq(i);
		for(int i=n;i<2*n;i++){
			pushq(i);
			popq(i);
			if(a[q[head]]-a[i-n]>=0) tot++;
		}
		printf("%d\n",tot);
	}
}