《藍橋杯每日一題》 字首和·Acwing 3956. 截斷數組

1.題目

https://www.acwing.com/problem/content/3959/

給定一個長度為 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：

輸入樣例3：

2
0 0
           

輸出樣例3：

2.思路分析

既然要配置設定三個非空子數組，且值相同，那麼不存在元素個數小于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);
    }
}
           

感謝你能看完， 如有錯誤歡迎評論指正，有好的思路可以交流一波，如果對你有幫助的話，點個贊支援下