题解 2018寒假训练1 C.非负和

问题 C: 非负和 时间限制: 1 Sec 内存限制: 128 MB [提交][状态][讨论版] 题目描述 罗老师给大家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 题解 ```cpp #include<stdio.h> using namespace std; int head,tail,k,sum[2000005],a[2000005],n,f[2000005],m,s; int min() { head=1; tail=0; for (int i=1;i<=n*2-1;i++) { while(head<=tail&&f[head]+m<=i) head++; while(head<=tail&&sum[i]<sum[f[tail]]) tail--; f[++tail]=i; if(i>=n) if (sum[f[head]]>=sum[i-n]) k++; } return 0; } int main() { scanf("%d",&n); m=n; s=0; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); s=s+a[i]; sum[i]=s; } for (int i=n+1;i<=n*2-1;i++) { a[i]=a[i-n]; s=s+a[i]; sum[i]=s; } min(); printf("%d",k); } ```