HDU 5783 Divide the Sequence

Problem Description Alice has a sequence A, She wants to split A into as much as possible continuous subsequences, satisfying that for each subsequence, every its prefix sum is not small than 0.   Input The input consists of multiple test cases.  Each test case begin with an integer n in a single line. The next line contains  n  integers  A1,A2⋯An . 1≤n≤1e6 −10000≤A[i]≤10000 You can assume that there is at least one solution.   Output For each test case, output an integer indicates the maximum number of sequence division.   Sample Input 6 1 2 3 4 5 6 4 1 2 -3 0 5 0 0 0 0 0   Sample Output 6 2 5   Author ZSTU   Source 2016 Multi-University Training Contest 5   Recommend wange2014

题意：给你一个序列，让你尽可能分成更多的子序列。 使得每个子序列的前缀和都大于或等于0 。 输出这个的子序列的总个数。 注意前缀和的概念 不会有像 3 2 1 -99 100 这样的非法数据 因为 有前缀和 小于0  根据概念 反过来扫 

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <cmath> #include <stack> #include <string> #include <map> #include <set> #define pi acos(-1) #define LL long long #define ULL unsigned long long #define inf 0x3f3f3f3f #define INF 1e18 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int, int> P; const int maxn = 1e6 + 5; LL a[maxn]; int main(void) { // freopen("C:\\Users\\wave\\Desktop\\NULL.exe\\NULL\\in.txt","r", stdin); int n, i, j; LL sum, cnt; while (~scanf("%d", &n)) { for (i = 1; i <= n; i++) scanf("%I64d", &a[i]); //用cin会T的 cnt = sum = 0; for (i = n; i >= 1; i--){ sum += a[i]; if (sum >= 0){ sum = 0; cnt++; } } printf("%I64d\n", cnt); } return 0; }