截断数组
侧边栏壁纸
  • 累计撰写 35 篇文章
  • 累计收到 10 条评论

截断数组

admin
2023-02-13 / 0 评论 / 273 阅读 / 正在检测是否收录...

题目
给定一个长度为 n
的数组 a1,a2,…,an

现在,要将该数组从中间截断,得到三个非空子数组。

要求,三个子数组内各元素之和都相等。

请问,共有多少种不同的截断方法?

输入格式
第一行包含整数 n

第二行包含 n
个整数 a1,a2,…,an

输出格式
输出一个整数,表示截断方法数量。

数据范围
前六个测试点满足 1≤n≤10

所有测试点满足 1≤n≤105
,−10000≤ai≤10000

输入样例1:
4
1 2 3 3
输出样例1:
1
输入样例2:
5
1 2 3 4 5
输出样例2:
0
输入样例3:
2
0 0
输出样例3:
0
分析
我们数组开辟100010个
输入从i=1开始
先对数组进行求一个前缀和,取前缀和最后一位得到总和,如果sum%3!=0那么这个数组是不能进行截断的
total%3==0,满足该条件下的数组是绝对可以进行截断
Test
我们对前缀和数组进行一个遍历
遍历sum[i]==total/3时 cns++;
sum[i]==total/3*2时 count++;
我们最后的结果其实就是res = count*cns
边界问题
for(int i=2;i<=n-1;i++)

i=2的原因:
因为说的是三份,非空,所以第一份数组必须至少包含i=1
i<=n-1的原因:
最后一个i=n;第三个数组必须至少包含i=n

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
long long sum[N];

int main()
{
    int n;
    long long cns=0,count=0,total=0,ave=0;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d",&a[i]);
        sum[i]=a[i];
        sum[i]+=sum[i-1];
        total+=a[i];
    }
    if(total%3!=0)
    {
        cout << "0"<<endl;
    }else{
        ave=total/3;
        for(int i=2;i<=n-1;i++)
        {
            if(ave==sum[i-1]) cns++;
            if(2*ave==sum[i]) count+=cns;
        }
        cout << count<<endl;
    }
}
0

评论 (0)

取消