给定一个长度为 n
的数组 a1,a2,…,an
现在,要将该数组从中间截断,得到三个非空子数组。
要求,三个子数组内各元素之和都相等。
请问,共有多少种不同的截断方法?
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n;
int s[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
s[i] += s[i -1];
}
if (s[n] % 3) {
printf("0");
return 0;
}
LL res = 0;
for (int i = 3, cnt = 0; i <= n; i++) {
// 记录i前面有多少个cnt可以使得成立
if (s[i -2] == s[n] / 3) cnt++;
// 如果i所处的位置满足条件加上它前面的cnt
if (s[n] - s[i -1] == s[n] / 3) res += cnt;
}
printf("%lld", res);
return 0;
}