acwing 3956 截断数组
题意解读
需要分为三个数组,且元素和相等,每个数组的元素和为原数组的1/3,不存在分配方案即为(原数组总和)%3!=0的情况
解题思路:
常规思路朴素暴力的想法:算好前缀直接双指针算法 这样 时间复杂度要爆掉
优化: 只用第二个数组最后一个数组 j 就可以了
只要保证 s[j]=2/3 s[n] 的条件下 去寻找 前面 1- (j-1) 里面有多少个满足=1/3s[n]的就好了 我们记下数就行
// as we all know int 2* 109次方
// 想想哪些数会爆掉?
//cn2 =5*10的9次方
#include<iostream>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int s[N],n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){ // 前缀和
int x;
scanf("%d",&x);
s[i]=s[i-1]+x;
}
if(s[n] % 3) puts("0");//当s[n]不是3的倍数,直接输出零
else{
LL cnt=0 , res=0;// res表示总数,cnt表示每一 |类| 的总数,
// 每次找到第二个并且满足,res就加上这类
for(int j=2;j<n;j++){
if(s[j-1] == s[n]/3) cnt++; //寻找第一刀 划分绿色区域
if(s[j] == s[n]/3*2) res+=cnt; //寻找第二刀 红色区域
}
cout<<res<<" ";
}
return 0;
}