思路:因为要将数组分为相等三份,可证明每一份都是sum / 3。那么第一份的前缀和应该为sum / 3; 第二份的应该为sum * 2 / 3。那么这个问题我们可以转化成在前缀和中sum * 2 / 3的值前有多少三个sum / 3;容易想到可以边求解边用cnt遍历到的sum / 3 的个数。其中要注意应该先求解,再统计。因为sum为零的情况下,会将自己也算在内。当然当n < 3可以直接特判答案为零。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int a[N], sa[N];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
sa[i] = sa[i - 1] + a[i];
}
if(n < 3 || sa[n] % 3 != 0)
{
printf("0");
return 0;
}
else
{
int ed = sa[n];
int st = ed / 3;
int mid = ed / 3 * 2;
int cnt = 0;
long long int sum = 0;
for(int i = 1; i < n; i ++)
{
if(sa[i] == mid)
{
sum = sum + cnt;
}
if(sa[i] == st)
{
cnt ++;
}
}
cout << sum << endl;
}
}