《蓝桥杯每日一题》 前缀和·Acwing 3956. 截断数组
《蓝桥杯每日一题》 前缀和·Acwing 3956. 截断数组
用户10604450
发布于 2024-03-15 14:41:50
发布于 2024-03-15 14:41:50
1.题目
给定一个长度为 n 的数组a1,a2,…,an。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？
输入格式
第一行包含整数 n。
第二行包含 n 个整数a1,a2,…,an。
输出格式
输出一个整数，表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10的五次方，−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：
02.思路分析
既然要分配三个非空子数组，且值相同，那么不存在元素个数小于3，不存在原数组总和%3!=0的情况
pres[]为前缀和数组，perSum=原数组总和/3
那么我们只需要找到一个位置 pres[i]==perSum*2
此时res+=（pres[1~i-1]==averge)即可
因为第i位 满足2*perSum，pres[i+1~n]==perSum
所以只需要加上能使前i位的数组 分为 两个值为averge的位置 的数量即可
3.Ac代码
import java.io.*;
public class Main {
static int N=100010;
public static void main(String[] args) throws IOException {
int n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
String []s=br.readLine().split(" ");
int []arr=new int[N];
//初始化初始数组
for (int i = 1; i <=n; i++) arr[i]=Integer.parseInt(s[i-1]);
int []pres=new int[N];
//求前缀和数组
for (int i = 1; i <=n; i++) pres[i]=pres[i-1]+arr[i];
//如果个数小于3，或者前缀和不是3的倍数，那么无法截断
if(n<3 ||pres[n]%3!=0){
System.out.println("0");
return;
}
long perSum=pres[n]/3,res=0,fir = 0,t=0;
//要给最后一个元素留下了，给第三个截断用
for (int i = 1; i <n; i++) {
t=pres[i];
if(t==perSum*2) res+=fir;
if(t==perSum) fir++;
//不能调换这两个if判断的原因是，如果当前t等于perSum和perSum*2时（比如0特判等），就会出现在同一位自加
//一旦出现自加，那么可以理解为中间那个截断元素个数为0，这是不可能的
}
System.out.println(res);
}
}感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录