前缀数组-截断数组

3956. 截断数组 - AcWing题库

不愧为acwing的中等题，细节是真的多，又又又阴沟翻船了。

题目要我们分成三个数组，求解又集几种分法。普遍思路是首先求解数组总和，除以3求的平均值。

第一个注意点：如果数组给的数的数量不足三个，那么返回0，如果总和除不尽3也返回0

接着我们查找几种分法，原理很简单，只要确定前两段得到分法并相乘就可以得出总分法。

因为不管前两段怎么分，剩下来的都是最后一段。那么关键问题是前两种的分法怎么求，在这里提供一种思路。我们求出前缀和后，找到一段距离，这段距离上的数字的和等于总和的三分之一，这就是第一段的最小分法子，为什么是最小分发？因为后面如果跟着0或者正负8，那么它的长度就会变长，而值不变。问题来了，如何确定第一段的最长的长度，并类推到第二段呢？我们不妨直接设个中间量aaaa，首先在前n-1个数字中寻找累加起来等于average的，找到一个aaaa++，一旦前缀和等于average*2，就证明已经到了第二段的最小长度，这时候就将answer+aaaa，为什么是加aaaa呢，原理就是总数等于第一段的数量乘以第二段的种类数，这是是把乘法变加法。

注意点：

之所以我令编号小于a，不仅仅是因为aa【a】等于average*3，还有一种特殊的样例，三个0，为了规避它的影响的，我设置这个条件，顺便

  if(aa[b]==average*2) {
		  answer=answer+aaaa;
	  }
	  if(aa[b]==average) {
		  aaaa++;
	  }

这一块代码也是规避0 0 0的影响的设置的

好啦，这题目就是这样

总代码：

import java.awt.geom.AffineTransform;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.function.IntBinaryOperator;
import java.util.function.LongBinaryOperator;

import javax.management.relation.InvalidRelationTypeException;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw1=new PrintWriter(System.out);
       String[] aStrings=br1.readLine().split(" ");
   int a=Integer.parseInt(aStrings[0]);
  aa=new long[a+1];
  String[] bStrings=br1.readLine().split(" ");
  int b;
  long sum=0;
  for(b=1;b<=a;b++) {
	  aa[b]=Long.parseLong(bStrings[b-1]);
	  aa[b]=aa[b]+aa[b-1];
	 
  }
  long average=aa[a]/3;
  if(aa[a]%3!=0||a<3) {
	  System.out.println(0);
	  return;
  }
  long answer=0;
  long aaaa=0;
  for(b=1;b<a;b++) {
	
	  if(aa[b]==average*2) {
		  answer=answer+aaaa;
	  }
	  if(aa[b]==average) {
		  aaaa++;
	  }
  }
  System.out.println(answer);
    }
    public static long[] aa;
}