fzu 1914 Funny Positive Sequence

题目链接：fzu 1914 Funny Positive Sequence

题目大意：给出n，以及长度为n的数列a[i]，现在以每个i为起点，计算d[i][j]表示以i为起点，计算后面j个数的和（如果i + j超过n，从1开始继续计算）问有几个i满足d[i][j]（1≤j≤n)均大于0。

解题思路：这题还是有点技巧的，从数组的后面枚举，碰到a[i] ≤ 0，就开始往前叠加，凡是和小于等于0的都是不满足情况的位置i。注意一个坑点就是，当叠加到i为0，即数组到头的时候sum仍小于0的时候，要考虑从后再遍历一下数组。

#include 
  
   
#include 
   
     #define ll long long const int N = 500005; int n, v[N]; ll a[N]; void init() { scanf("%d", &n); memset(v, 0, sizeof(v)); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); } int solve() { int ans = n; ll sum = 0; for (int i = n - 1; i >= 0 && ans; i--) { if (sum <= 0) { sum += a[i]; if (sum <= 0) { ans--; v[i] = 1; } } else if (a[i] <= 0) { sum = a[i]; ans--; v[i] = 1; } } int i = n - 1; while (sum <= 0) { sum += a[i]; if (sum <= 0 && !v[i]) { v[i] = 1; ans--; } i--; if (ans == 0 || i < 0) break; } return ans; } int main () { int cas; scanf("%d", &cas); for (int i = 1; i <= cas; i++) { init(); printf("Case %d: %d\n", i, solve()); } return 0; }