题解 | 喜欢切数组的红（前缀和）
喜欢切数组的红
https://www.nowcoder.com/practice/74cb703f25dc4956acb3b08028a1f4b4
#牛客春招刷题训练营# + 链接
1.区间和的条件不好处理，转换为总和的三分之一以及前缀和。
2.区间内至少有一个正数，转换为下一个正数的索引。
3.向后计数，转换为计数的后缀和。
#include <iostream>
using namespace std;
using ll = long long;
const int MAXN=200010;
int a[MAXN], ddr[MAXN], np[MAXN];
ll s[MAXN];
int main() {
int n;
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%d",a+i);
for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
int x=n+1;
for (int i=n;i>0;i--) {
np[i] = x;
if (a[i]>0) x=i;
}
ll mm = s[n]/3;
if (mm*3!=s[n]) {
puts("0");
return 0;
}
ll ans=0;
for (int i=n;i>0;i--) {
ddr[i] = ddr[i+1]+ (s[i]==mm*2);
}
for (int i=1;i<=n;i++) {
if (s[i]==mm) ans+=ddr[np[i]];
}
printf("%lld\n", ans);
return 0;
}
网易游戏公司福利 622人发布
