luo1046-----非负和 题解

题目

非负和

题目描述

罗老师给大家n个数字：a1,a2,a3, .. , an。
这些数字可以循环，ai, ai+1, ai+2, … , an, a1, a2, … , ai-1。
显然，这样的循环有n种。
现在问大家，n种中有多少种保证从第一项到任意项的和大于等于0
比如
3
-1 1 1
有三种：
-1 1 1
1 1 -1
1 -1 1
其中第一种第一项到第1,2,3项的和分别为： -1， 0， 1
第二种第一项到第1,2,3项的和分别为： 1， 2， 1
第三种第一项到第1,2,3项的和分别为： 1， 0， 1
所以第二种和第三种符合，答案为2

输入

输入n

然后输入n个数字ai

输出

输出有多少种符合

样例

输入

3
-1 1 1

输出

2

提示

【数据规模和约定】
1<=n<=1000000
-1000<=ai<=1000

补充

时间限制 2 秒
内存限制 128 MB
来源 luo’s OJ

题解

luo1428—–区间最小最大值的加强版
直接上！

#include <bits/stdc++.h>
using namespace std;
int n,t,w,chen_zhe;
int a[2000010],sum[2000010],kkksc03[2000010],id[2000010];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	for (int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
		a[i+n] = a[i];
	}
	for (int i = 1; i <= 2*n; i++){
		sum[i] = sum[i-1]+a[i];
	}
	t = w = 1;
	kkksc03[1] = sum[1];
	id[1] = 1;
	for (int i = 2; i <= n; i++){
		while (sum[i] < kkksc03[w]){
			w--;
			if (w < t){
				break;
			}
		}
		w++;
		kkksc03[w] = sum[i];
		id[w] = i;
	}
	if (kkksc03[t] >= 0){
		chen_zhe++;
	}
	for (int i = n+1; i <= 2*n-1; i++){
		while (id[t] < i-n+1){
			t++;
			if (t > w){
				break;
			}
		}
		if (w >= t){
			while (sum[i] < kkksc03[w]){
				w--;
				if (w < t){
					break;
				}
			}		
		}
		w++;
		kkksc03[w] = sum[i];
		id[w] = i;
		if (kkksc03[t]-sum[i-n] >= 0){
			chen_zhe++; 
		}
	}
	printf("%d",chen_zhe);
	return 0;
}

测评结果 通过
分数 100
耗时 721 MS
内存 33428 KB
语言 C++
代码长度 983 bytes