解题思路

先设前缀和数组为 $pre$ ，其中

pre[i]=a_1+a_2+\cdots+a_i

并约定 $pre[0]=0$ 。

P4585.第3题-天才的数列切割

1000ms

Difficulty: 6

所属公司 : 携程

算法与标签>前缀和

给定一个长度为 $n$ 的数组 { $a_1，a_2,...,a_n$ }。你将对数组进行若干次“切割”操作，操作规则如下：

一开始，数组段集合仅包含整段 $[1,n]$ ;
每次操作，必须从“当前数组段集合”中选择一段完整的数组段 $[l,r]$ (该段长度需严格大于 $2$ )，然后选择一个位置 $mid(l<mid≤r)$ ，若满足：

$\sum_{i=l}^{m i d-1} a_{i}=\sum_{i=m i d}^{r} a_{i}$

则可以把该数组段分成两段 $[l,mid-1]$ 与 $[mid,r]$ ，并以这两段替换原来的 $[l,r]$ ，继续加入到数组段集合中;

所有区间均以原数组的下标表示，不进行重新编号;切割后得到的两个区间互不重叠，且并集为原区间。请你计算，在最优策略下，总共最多能进行多少次切割。

第一行输入个整数 $n(1≤n≤10^6)$ 表示数组的长度

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n (1≤a_i≤10^9)$ 表示数组中的元素。

输出一个整数，表示最多的切割次数，若不存在任何合法的切割方案，输出 $0$ 。

输入

6
1 2 1 1 1 2

输出

说明

对全段 $[1,6]$ ，可在 $mid=4$ 处切割，因为 $1+2+1=1+1+2$ 。得到 $[1,3]$ 与 $[4,6]$ 。随后 $[4,6]$ 在 $mid=6$ 处再次切割，因为 $1+1=2$ 。总共进行了 $2$ 次切割。

输入

预期输出（选填）