正经题解｜魔剑亚托克斯

题意分析

寻找长度为$n$的所有非空前缀，求解在前缀当中是否存在数字$a_i$等于其他数字总和。

算法分析

$a_i$的取值决定了它一定为正数，那么我们只需要找到 唯一 与其他所有元素相加的元素相等即为符合条件的元素。

我们可以去检查下标$1$至$n$之间的每一个前缀$i$，是否满足条件$sum(a_1,a_2...a_i) - max(a_1,a_2,...a_i) = max(a_1,a_2,...a_i)$。若满足则为符合条件的数字序列之一，采用for循环进行枚举即可

时间复杂度分析

$O(n)$

STD标程

#include <iostream>
using namespace std;

int main(){
	int n; cin >> n;
	int a[n];
	for(int i = 0; i < n; i++)
		cin >> a[i];
	long long sum = 0;
	int mx = 0, ans = 0;;
	for(int i = 0; i < n; i++){
		sum += a[i];
		mx = max(mx, a[i]);
		if(sum - mx == mx) 
			ans++;
	}
	cout << ans << endl;
	return 0; 
}