思想:
res
,循环遍历前缀和数组 a
。i
为分割点,若 a[i] == res
,说明将 i
作为分割点有可能成立,记录分割点数量为 cnt ++
。n - i + 1
为第二个分割点,若 a[n] - a[n - i + 1] == res
,则说明该分割点可以与 i
之前的所有分割点进行分割数组,记录分割方案为 ans += cnt
。代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
typedef long long LL;
LL a[N];
void solve(){
int n; cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i]; a[i] += a[i - 1];
}
if(n < 3 || a[n] % 3 != 0){ //特殊情况
cout << 0 << endl;
return ;
}
else{
LL res = a[n] / 3;
LL cnt = 0, ans = 0;
for(int i = 1; i + 2 <= n; i ++){
if(a[i] == res) cnt ++;
if(a[n] - a[i + 1] == res) ans += cnt;
}
cout << ans << endl;
}
}
int main(){
solve();
return 0;
}