黑苹果岛

题目描述

代码勇者来到了苹果岛上，苹果岛上有两种苹果：随处可见的红苹果与非常难吃的黑苹果。

勇者的初始代码能力为 $1$，他每吃下一个红苹果，代码能力就会得到一定程度的提升（每个红苹果带来的提升可能是不同的，甚至也可能是负的）；他每吃下一个黑苹果，代码能力就会直接清零。

岛上的苹果仙子用 $n$ 个红苹果招待了勇者，同时还给了他一个黑苹果。勇者必须按照仙子规定的顺序吃红苹果，但是他可以在吃任意一个红苹果之后吃黑苹果。

勇者想知道他应该在什么时候吃黑苹果，才能在离开苹果岛的时候的代码能力最大。

输入格式

第一行输入两个正整数 $n$（$n\le10^5$）。

第二行输入 $n$ 个整数 $a_i$（$1\le|a_i|\le 10$）。

输出格式

输出一个整数 $x$，表示勇者应该在吃第 $x$ 个红苹果之后吃黑苹果，才能使他离开苹果岛的时候的代码能力最大（如果有多个 $x$ 满足条件，输出最小的一个）。

或者输出 $0$ ，表示勇者不应该吃黑苹果。

样例 #1

样例输入 #1

5
1 -2 3 -6 5

样例输出 #1

4

提示

如果不吃黑苹果，离开时代码能力为 $1$

在吃第 $1$ 个红苹果之后吃黑苹果，离开时代码能力为 $0$

在吃第 $2$ 个红苹果之后吃黑苹果，离开时代码能力为 $2$

在吃第 $3$ 个红苹果之后吃黑苹果，离开时代码能力为 $-1$

在吃第 $4$ 个红苹果之后吃黑苹果，离开时代码能力为 $5$

在吃第 $5$ 个红苹果之后吃黑苹果，离开时代码能力为 $0$

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[1000007],ans[1000007],QwQ;
int main(){
	cin >> n;
	for(int i = 1;i <= n; ++i){
		cin >> a[i];
	}
	for(int i = 0;i <= n; ++i){
		if(i == 0){
			for(int j = 1;j <= n; ++j){
				ans[0] += a[j];
			}
		}
		if(i >= 1){
			for(int j = i+1;j <= n; ++j){
				ans[i] += a[j]; 
			}
		}
	}
	for(int i = 0;i <= n; ++i){
		if(ans[i] < ans[i+1]  && i != 0){
			QwQ = i;
		}else{
			QwQ= i-1;
		}
		//cout << ans[i] << " ";
	}
	cout << QwQ;
	return 0;
}

悬赏互关