分数: 366 分
问题陈述
高桥在一家搬家公司做兼职。今天的工作是加载 N 包裹在仓库里排成一排,装到卡车上。的重量 i左边第一个包是 W_i 公斤。
卡车根据需要拥有任意多个平台。在将软件包分发到平台上时,高桥遵循以下规则。
规则:
划分行 N 打包成 一组或多个连续包裹 没有间隙,并将每一组加载到一个平台上。即每个包都被加载到同一个平台上,并且加载到同一平台上的包在原始行中是连续的。此外, 每个平台的包裹总重量必须相等.
高桥希望使用尽可能多的平台(因为平台越多,每个平台的负载就越轻,装卸变得更容易)。
根据上述规则求出分发包时可以使用的最大平台数。
请注意,仅使用一个平台并将所有包加载到该平台上始终满足规则,因此始终存在有效的发行版。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9
- 所有输入均为整数
输入
N W_1 W_2 \ldots W_N
- 第一行包含一个整数 N 代表包裹数量。
- 第二行包含 N 整数 W_1, W_2, \ldots, W_N 用空格分隔,其中 i- 第一个整数表示权重 i左边第一个包。
输出
在一行上打印可以使用的最大平台数。
示例输入 1
6 1 2 3 3 2 1
示例输出 1
4
示例输入 2
10 2 4 2 2 6 4 2 2 8 8
示例输出 2
5
示例输入 3
15 1000000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 1000000000 500000000 500000000 1000000000
示例输出 3
12