本文最后更新于 722 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 前缀和。
- 特殊情况:
- 当数组元素小于三个时,无解。
- 当该数组所有数之和不为 3 的整数倍时,无解。
- 设数组均分的值为
res
,循环遍历前缀和数组 a
。
- 设
i
为分割点,若 a[i] == res
,说明将 i
作为分割点有可能成立,记录分割点数量为 cnt ++
。
- 设
n - i + 1
为第二个分割点,若 a[n] - a[n - i + 1] == res
,则说明该分割点可以与 i
之前的所有分割点进行分割数组,记录分割方案为 ans += cnt
。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 1e6 + 3; |
| |
| typedef long long LL; |
| |
| LL a[N]; |
| |
| void solve(){ |
| int n; cin >> n; |
| for(int i = 1; i <= n; i ++){ |
| cin >> a[i]; a[i] += a[i - 1]; |
| } |
| if(n < 3 || a[n] % 3 != 0){ |
| cout << 0 << endl; |
| return ; |
| } |
| else{ |
| LL res = a[n] / 3; |
| LL cnt = 0, ans = 0; |
| for(int i = 1; i + 2 <= n; i ++){ |
| if(a[i] == res) cnt ++; |
| if(a[n] - a[i + 1] == res) ans += cnt; |
| } |
| cout << ans << endl; |
| } |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |