AcWing 3956. 截断数组
原题链接
中等
作者:
dss_zhs
,
2023-02-13 22:09:39
,
所有人可见
,
阅读 136
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N];
int main(){
cin >> n;
//输入数组,计算前缀和
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] += a[i - 1];
}
//特判,非3倍数结果为零
if(a[n]%3){
cout << "0" << endl;
return 0;
}
LL ans = 0;
for(int i = 3, cnt = 0; i <= n; i++){
if(a[i - 2] == a[n]/3) cnt++;//第一个截断位置 (从第一个前缀和数组开始,1~j)
if(a[n] - a[i - 1] == a[n]/3) ans += cnt;//第二个截断位置 (用数组总和减,i~n)
}
cout << ans <<endl;
return 0;
}