前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >截断数组

截断数组

作者头像
凡尘扰凡心
发布2023-02-27 15:04:55
7380
发布2023-02-27 15:04:55
举报
文章被收录于专栏:默认分类

题目 给定一个长度为 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,满足该条件下的数组是绝对可以进行截断

我们对前缀和数组进行一个遍历 遍历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

代码语言:javascript
复制
#include 
#include 
#include 
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"<
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档