题目描述
代码勇者来到了苹果岛上,苹果岛上有两种苹果:随处可见的红苹果与非常难吃的黑苹果。
勇者的初始代码能力为 11,他每吃下一个红苹果,代码能力就会得到一定程度的提升(每个红苹果带来的提升可能是不同的,甚至也可能是负的);他每吃下一个黑苹果,代码能力就会直接清零。
岛上的苹果仙子用 nn 个红苹果招待了勇者,同时还给了他一个黑苹果。勇者必须按照仙子规定的顺序吃红苹果,但是他可以在吃任意一个红苹果之后吃黑苹果。
勇者想知道他应该在什么时候吃黑苹果,才能在离开苹果岛的时候的代码能力最大。
输入格式
第一行输入两个正整数 nn(n\le10^5n≤10
5
)。
第二行输入 nn 个整数 a_ia
i
(1\le|a_i|\le 101≤∣a
i
∣≤10)。
输出格式
输出一个整数 xx,表示勇者应该在吃第 xx 个红苹果之后吃黑苹果,才能使他离开苹果岛的时候的代码能力最大(如果有多个 xx 满足条件,输出最小的一个)。
或者输出 00 ,表示勇者不应该吃黑苹果。
输入输出样例
输入 #1复制
5
1 -2 3 -6 5
输出 #1复制
4
说明/提示
如果不吃黑苹果,离开时代码能力为 11
在吃第 11 个红苹果之后吃黑苹果,离开时代码能力为 00
在吃第 22 个红苹果之后吃黑苹果,离开时代码能力为 22
在吃第 33 个红苹果之后吃黑苹果,离开时代码能力为 -1−1
在吃第 44 个红苹果之后吃黑苹果,离开时代码能力为 55
在吃第 55 个红苹果之后吃黑苹果,离开时代码能力为 00
其实就是问你前m项相加最小,m值是多少
比如前3个苹果吃完变成-10,是所有组合里最小的,此时吃黑苹果相当于+10
而如果苹果都是正数,那么m值为0,就应该最先吃黑苹果
那怎么求m呢,其实非常简单,就跟求数组里最小值是一样的,只不过跟min相比较的值不是a[i]而是它们到目前为止的和sum
只要遇到比当前min值小的就把当前的i记录下来
所以根本没有必要事先把输入都存数组里,可以直接输入一个就相加然后跟min去比较
一个循环就搞定