题目描述
暴恐龙每天都需要吃 N 个食物。为了营养均衡，饲养员也会投喂一些恐暴龙不爱吃的食物。好吃的食物会增加心情值，不好吃的会减少。当心情值少于 0 时（恐暴龙心情值初始为 0），恐暴龙会将饲养员吃掉。 为了避免被吃，饲养员可以选择从中间开始喂食，例如：有 N 个食物，饲养员可以从k,k+1,k+2...N,1,2...k-1 这种顺序喂食。 饲养员想要直到有多少种 K，从 K 开始喂到 N 然后从 1 喂食到 K-1 可以避免自己不被吃掉。
输入输出格式
输入格式
第一行有一个整数 N，表示有 N 个食物。 第二行有 N 个整数，按顺序给出第 i 个食物喂食后所能导致的心情值变化 ai。数据中间用一个空格隔开。
输出格式
输出一个整数，表示可行的方案个数。
输入输出
样例1
输入： 4 -3 5 1 2
输出： 2
解释： 有 [5 1 2 -3] 或 [1 2 -3 5] 两种情况。
样例2
输入： 6 2 -3 5 5 -4 -5
输出： 1
说明提示
1≤N≤106 −100≤ai≤1000
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1000005; int n; int a[maxn], b[maxn]; int main() { cin >> n; for (int i = 1; i <= n; i++) {//维护前缀和 cin >> a[i]; if (i == 1) { b[i] = a[i]; } else { b[i] = b[i - 1] + a[i]; } } int ans = 0; for (int i = 1; i <= n; i++) {//遍历n个食物（第几个食物作为k） int flag = 0; int u = i - 1; int uu = 0; for (int j = i; j <= n; j++) {//k~n:此时心情为（第j个食物前缀和-第k-1个食物前缀和） if (b[j] - b[u] < 0) { flag = 1; break; } if (flag == 0 && j == n) { uu = b[n] - b[u];//记录吃到第n个食物时的心情值 } } if (flag == 0) { for (int j = 1; j <= i - 1; j++) {//1~k-1:此时心情为（吃到第n个食物时的心情+第j个食物前缀和） if (uu + b[j] < 0) { flag = 1; break; } } if (flag == 0) { ans++; } } } cout << ans; }
