学步园

解题方法

经过简单分析后发现, 如果输入的 n 个数加起来的和是 Sum

只有当 Sum % 3 == 0 时才可能有分割的方法, 这时每一份分割后的数的和都是 Sum / 3

既然考虑的都是一段数的和那么很容易就可以联想到使用前缀和 

前缀和是指 前面一部分数的和

例如前面的例子给出4个数 -> 1 2 3 3

那么 sum[1] = 1, sum[2] = 3, sum[3] = 6, sum[4] = 9 (sum[i]表示前缀 1-i 的和)

如果我们要 求出第2个数到第3个数的和的话就可以用 sum[3]-sum[1] (sum[3]表示a[1]+a[2]+a[3], sum[1]表示a[1], 那么sum[3]-sum[1]就是a[2]+a[3])

所以对于输入的 n 个数的 n 个前缀 sum[1] -> sum[n] 如果 sum[i] == Sum / 3的话就说明从 a[1]+a[2]+...+a[i]的和等于 Sum / 3

我们可以用一个变量 cnt1 表示有多少个前缀的和等于 Sum / 3

遍历 sum 数组时

  for( int i=1; i<=n; i++）{

    if(sum[i] == Sum / 3) cnt1++;

    else if(sum[i] == Sum / 3 * 2) res += cnt1; // 当 a[1]+a[2]+...+a[i] == Sum / 3 * 2时如果前面有一个sum[x] == Sum / 3的话

                                                // 不就说明 a[1]+a[2]+...+a[x] == Sum / 3 && a[x+1]+a[x+2]+...+a[i] == Sum / 3 &&

                                                // a[i+1]+a[i+2]+...+a[n] == Sum / 3了吗, 这就意味着有一个可行解

  }                  

注意

1.方法数有可能超 int , 所以保存方法数的变量要用 long long

2.当输入的数的和等于0的时候要特判下, 具体看代码

参考代码 - 有疑问的地方在下方留言 看到会尽快回复的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;
LL sum[MAXN];

int main() {
  int n;
  while(scanf("%d", &n) != EOF) {
    sum[0] = 0;
    int t;
    for( int i=1; i<=n; i++ ) {
      scanf("%d", &t);
      sum[i] = sum[i-1] + t;
    }
    if(sum[n] % 3) {
      printf("0\n");
    }
    else {
      int tn = 0;
      LL res = 0;
      for( int i=1; i<=n; i++ ) {
        if(sum[n] == 0) {
          if(sum[i] == 0) {
            if(i > 1 && i < n) {
              res += tn;
            }
            tn++;
          }
        }
        else if(sum[i] == sum[n]/3) tn++;
        else if(sum[i] == sum[n]/3*2) {
          res += tn;
        }
      }
      cout<<res<<endl;
    }
  }
  return 0;
}