本文最后更新于615 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com
题目
给定一个长度为 n的数组 a1,a2,…,an。
现在,要将该数组从中间截断,得到三个非空子数组。
要求,三个子数组内各元素之和都相等。
请问,共有多少种不同的截断方法?
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一个整数,表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤1e5,−10000≤ai≤10000。
输入样例1:
4
1 2 3 34
1 2 3 3
输出样例1:
1
输入样例2:
5
1 2 3 4 5
输出样例2:
0
输入样例3:
2
0 0
输出样例3:
0
思路:
1.分为三个数组,并且和相等,也就意味着每个部分都是总和的1/3
2.总和必须能整除3
3.相当于要在数组上找两个位置,第一个位置 sum/3,第二个位置 (sum/3)*2
4.这两个位置可取的点都有若干个,那么它们的全部组合为(第一个位置可取的点)*(第二个位置可取的点)
//注意数据范围
代码:
#include<iostream>
using namespace std;
long long sum[100005];
long long n, tmp,ans;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> sum[i];
sum[i] += sum[i - 1];
}
if (sum[n] % 3 != 0)ans = 0;
else
{
long long cnt = 0;
tmp = sum[n] / 3;
for (int i = 1; i < n; i++)
{
if (sum[i] == 2 * tmp)ans += cnt;
if (sum[i] == tmp)cnt++;
}
}
cout << ans;
}