AcWing 3956. 截断数组
原题链接
中等
作者:
和光同尘_80
,
2023-02-13 22:04:39
,
所有人可见
,
阅读 127
最短代码
思路
- 一个数组可以三等分,我们可以想到,求sum/3的值,记作ave,这是第一步
- 第二部求前n项和,如果我求的tot[n]是ave,先记录下来
- 如果tot[n]是2ave,说明到最后还剩下ave,在2 `ave之前,看看有多少个ave就行
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
LL a[N],s[N];
LL n,ans=0,avg=0;
int main(){
cin>>n;
for (int i = 1; i <= n; i ++ )scanf("%lld",&a[i]),a[i]+=a[i-1];//注意这里的输入格式
if(a[n]%3){
cout<<"0"<<endl;
}
else{
avg=a[n]/3;
LL p=0;
for(int i=1;i<n;i++){
if(a[i]==2*avg)ans+=p;
if(a[i]==avg)p++;
}
printf("%lld",ans);
}
return 0;
}