Codeforces - 466C - Number of Ways

Question

题目大意

就是给你一个数组，要将这个数组分成和相等的三个部分，问你有多少种分法。

解析

解法很奇妙:

• 首先计算出每个位置的前缀和 sums[i] ，整个数组的和存在 sums[n-1] 中；
• 因为要分成三部分，所以 sums[n-1] % 3 一定要等于 0 ，不然就没有解，输出 0 即可；
• 然后就遍历整个数组，记 sums[n-1]/3 = avg ，看 sums[i] == avg 和 sums[i] == 2 * avg 的位置，然后使用两个变量 res 和 cnt 统计，其中的玄机也是很巧妙。统计的顺序可以从 n-2 ~ 0 ，也可以从 0 ~ n-2 ( n-1 是第三个部分，不要算进去)。看两个例子就能体会到了。

注释部分是从 n-2 ~ 0 ，非注释部分是从 0 ~ n-2 :

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = cin.nextInt();
        long[] sums = new long[n];
        sums[0] = arr[0];
        for(int i = 1; i < n; i++)
            sums[i] = sums[i-1] + arr[i];
        // each part is S/3
        if(sums[n-1]%3 != 0){
            System.out.println(0);
            return;
        }
        long avg = sums[n-1]/3;
        long cnt = 0, res = 0;
//        for(int i = n-2; i >= 0; i--){ // 必须从 n-2 开始,从 n-1 会出错,因为 n-1 是第 3 个 S/3 了
//            if(sums[i] == avg)  // 这个必须在下面 cnt+=1 之前
//                res += cnt;
//            if(sums[i] == avg*2)
//                cnt += 1;
//        }
        for(int i = 0; i < n-1; i++){ // 必须只能到 n-2,到 n-1 会出错,因为 n-1 是第 3 个 S/3 了
            if(sums[i] == avg*2) // 这个必须在下面 cnt+=1 之前
                res += cnt;
            if(sums[i] == avg)
                cnt += 1;
        }
        System.out.println(res);
    }
}