摘要
Title: 3956. 截断数组
Tag: 枚举、前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

3956. 截断数组

• 题意

  给定一个长度为 n的数组 a1,a2,…,an
  现在，要将该数组从中间截断，得到三个非空子数组。
  要求，三个子数组内各元素之和都相等。
  请问，共有多少种不同的截断方法？

• 思路

  首先，如果要平均三份，总和必须是3的倍数，且长度大于等于3
  其次枚举两次刀的位置

  • 第一刀，只要保证后面留俩元素即可，且前面的和等于avg
  • 第二刀，必须在第一刀的后两个位置，因为要给第二组至少留一个元素

• 代码

  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int
  
  #define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int N = 1e5 + 10, INF = 0x3f3f3f3f;
  
  int n, sum;
  int a[N], b[N];
  int tot, cnt1, cnt2;
  signed main()
  {
      IOS;
      cin >> n;
      for (int i = 1; i <= n; ++i)
      {
          cin >> a[i];
          sum += a[i];
          b[i] = b[i - 1] + a[i];
      }
      if (n < 3 || sum % 3)
      {
          cout << "0\n";
          return 0;
      }
      int avg = sum / 3;
      for (int i = 1; i < n; ++i)
      {
          // 针对每一个位置进行判断
          if (b[i] == avg) // 第一部分
              cnt1++;
          if (b[n] - b[i + 1]) // 第二刀，分开二三数组，所以第二刀最小只能在i+2，因为必须留出一个给第二组
              cnt2 += cnt1;
      }
      cout << cnt2 << '\n';
      return 0;
  }