截断数组
数组 截断
2023-06-13 09:16:59 时间
题目 给定一个长度为 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
#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;
}
}
相关文章
- 字符数组初始化为空
- 【说站】Java数组如何实现动态初始化
- vue改写数组方法_vue数组添加和删除
- 【算法基础】数组扩容、缩容
- Java的数组冒泡排序法
- 2023-01-06:给定一个只由小写字母组成的字符串str,长度为N,给定一个只由0、1组成的数组arr,长度为N,arr[i
- 截断数组
- PHP- 复合数据类型-数组的注意事项
- PHP each():返回数组当前元素的键值对
- Shell编程之数组使用详解程序员
- php 数组索引值重新从0开始递增方法详解编程语言
- PHP遍历数组
- Numpy dtype定义复合类型数组过程详解
- 轻松操作MySQL数组表(mysql数组表)
- Exploring the Power of Oracle in Array Handling: A Comprehensive Guide(oraclein数组)
- php中判断数组是一维,二维,还是多维的解决方法
- js数组去重的常用方法总结
- JS二维数组的定义说明
- 用javascript对一个json数组深度赋值示例