1000ms

Difficulty: 5

所属公司 : 拼多多

时间 :2025年10月26日

算法与标签>贪心算法

会员或题库专享

请先，开通会员或购买题库拼多多机考题库，可解锁完整内容。

购买拼多多机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（拼多多机考题库），可解锁完整内容。

购买题库开通会员

解题思路

我们把每次“相邻合并”看作把数组切成若干段、每段内部合并成一个数（为该段元素和）。
若最终都相等，则必然能把数组划分为连续的 $K$ 段，每段和均为同一个值 $S$ ，且总和 $\text{SUM}=\sum a_i=K\cdot S$ 。
操作次数 = 初始长度 $n$ 减去剩余段数 $K$ ：最少操作数 $= n-K$ 。因此问题转化为：最大化可行的段数 $K$ 。

关键观察：

第一段是一个前缀，所以段和 $S$ 必为某个前缀和；

题目内容

多多有一个长度为 $n$ 从左到右依次排列的数组 $a_1,a_2,...,a_n$ 。

多多可以对这个数组进行任意次操作,每次操作可以选择数组中两个相邻的数，把它们合并成一个新数(新数的值为两数之和)，合并后数组长度减少 $1$ .

多多想知道，最少需要多少次这样的操作，才能让数组中所有数都相等