AcWing 3956. 截断数组JAVA
原题链接
中等
作者:
宝宝蛋
,
2023-02-13 21:44:04
,
所有人可见
,
阅读 144
JAVA 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static final int N =100010;
static int a[] = new int[N];
static int s[] = new int[N];
static long res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String str[] = br.readLine().split(" ");
for(int i=1;i<=n;i++) {
a[i]=Integer.parseInt(str[i-1]);
//前缀和处理
s[i]+=s[i-1]+a[i];
}
if(s[n]%3 != 0) {
//不能划分为三等份
System.out.println("0");
return;
}
long count=0;
//以第二刀来进行枚举,保证第一部分和第三部分不为空,第二刀范围2~n-1
for(int i=2;i<n;i++) {
//i前面之和为总和的1/3,则此时第一刀的选择加1,count++
if(s[i-1] == s[n]/3)count++;
//s[n]-s[i]=总和的1/3,则此时是合适的二刀,res加上此前的count值
if(s[n]-s[i] == s[n]/3){
res+=count;
}
}
System.out.println(res);
}
}