将数组截断成三段,相当于切两刀
#include<iostream>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int a[N],s[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//构造前缀和数组
if(n<3||s[n]%3!=0)//如果长度小于3或者不是3的倍数,直接输出0
{
cout<<0<<endl;
return 0;
}
ll res=0,cnt=0;
for(int i=1;i<n;i++) //计算可能为第二刀的位置
{
if(s[i]==s[n]/3*2) cnt++;
}
for(int i=1;i<n;i++)//枚举第一刀
{
if(s[i]==s[n]/3*2) cnt--;//如果该位置可以为第二刀,则减去
if(s[i]==s[n]/3) //如果这个位置是总和的1/3则可以为第一刀
{
res+=cnt;//该位置加上第二刀的数量
}
}
cout<<res<<endl;
return 0;
}
你这个方法挺不错的
看y总看不懂,这个秒懂了
没懂枚举第一刀的做法,为什么可以是第二刀的时候要减1
因为一种分法需要切两刀,第二刀的位置肯定要在第一刀后面; 第一个循环是所有可以切第二刀的地方,第二个循环减去的是不能再用的
不知道对不对
妙
这个方法真好,画个图更爽更清晰
明天补一个
怎么还没补(狗头)
怎么还没补(狗头)