解题思路

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

关键观察：

1. 第一段是一个前缀，所以段和 $S$ 必为某个前缀和；
2. $S$ 必须整除总和 $\text{SUM}$，且 $S\ge \max(a_i)$（单个元素不能被再拆分）；
3. 若选择某个前缀和 $x$ 作为 $S$，只需检查所有倍数 $x,2x,\dots,(K-1)x$ 是否都出现在“前缀和集合”中（这些位置即为切割点）。若存在，则可分成 $K=\text{SUM}/x$ 段。

实现要点（贪心+哈希）：

• 预处理所有前缀和与其哈希集合 set（不含完整和 SUM）；

• 将所有前缀和按从小到大枚举为候选 $S$：

  • 跳过不满足 $x\ge \max(a_i)$ 或 $\text{SUM}\bmod x\ne 0$ 或 $K=\text{SUM}/x>n$ 的 $x$；
  • 依次判断 $x,2x,\dots,(K-1)x$ 是否都在集合里；若是，更新最大段数 bestK=max(bestK, K)；

• 初始 bestK=1（全部合并成一个数总是可行）；答案为 n - bestK。

该做法只对“是前缀和且整除 SUM”的候选进行验证；前缀和严格递增，验证总次数满足调和级数界，效率可控。

复杂度分析

• 预处理前缀和与哈希：$O(n)$；对前缀和排序：$O(n\log n)$。
• 对每个候选 $x$ 的验证需要检查约 $\text{SUM}/x$ 个倍数。由于前缀和最小递增为 1，$\sum \limits_{x\in \text{prefix}}$ $\text{SUM}/x \le n\cdot H_n$=$O(n\log n)$。
• 整体时间复杂度：$O(n\log n)$；空间复杂度：$O(n)$。

代码实现

Python

# 题意：最少相邻合并次数使所有数相等
# 思路见上。注意：本题输入为空格分隔数字，无法用 literal_eval 直接解析，使用标准拆分读取。

import sys

def min_operations(a):
    n = len(a)
    S = sum(a)
    mx = max(a)

    # 前缀和列表（不含总和），以及集合便于 O(1) 判在
    pref = 0
    pref_list = []
    pref_set = set()
    for i in range(n - 1):
        pref += a[i]
        pref_list.append(pref)
        pref_set.add(pref)

    pref_list.sort()  # 从小到大尝试，使可能的段和尽量小，从而段数尽量大

    bestK = 1  # 至少可全部合并成一个数
    for x in pref_list:
        if x < mx:
            continue
        if S % x != 0:
            continue
        K = S // x
        if K > n:
            continue
        # 检查 x, 2x, ..., (K-1)x 是否都在前缀和集合中
        ok = True
        t = x
        # 第一个 t==x 一定在集合（因为 x 来自前缀列表），可从 2x 开始也行
        while t < S:
            if t not in pref_set:
                ok = False
                break
            t += x
        if ok:
            if K > bestK:
                bestK = K
            if bestK == n:
                break  # 已经最优

    return n - bestK

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    T = next(it)
    out_lines = []
    for _ in range(T):
        n = next(it)
        arr = [next(it) for _ in range(n)]
        out_lines.append(str(min_operations(arr)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 题意：最少相邻合并次数使所有数相等
// 使用前缀和 + HashSet 校验候选段和。
// 由于 n up to 1e5，采用 BufferedInputStream 简易快读。

import java.io.*;
import java.util.*;

public class Main {

    // 简易快读
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        long nextLong() throws IOException {
            int c; do { c = read(); } while (c <= ' ' && c != -1);
            long sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    static long minOperations(long[] a) {
        int n = a.length;
        long S = 0, mx = 0;
        for (long v : a) { S += v; if (v > mx) mx = v; }

        long pref = 0;
        ArrayList<Long> prefList = new ArrayList<>(Math.max(0, n - 1));
        HashSet<Long> prefSet = new HashSet<>(Math.max(16, n * 2));
        for (int i = 0; i < n - 1; i++) {
            pref += a[i];
            prefList.add(pref);
            prefSet.add(pref);
        }

        Collections.sort(prefList);
        long bestK = 1; // 全并为一段总是可行
        for (long x : prefList) {
            if (x < mx) continue;
            if (S % x != 0) continue;
            long K = S / x;
            if (K > n) continue;

            boolean ok = true;
            long t = x;
            while (t < S) {
                if (!prefSet.contains(t)) { ok = false; break; }
                t += x;
            }
            if (ok) {
                if (K > bestK) bestK = K;
                if (bestK == n) break;
            }
        }
        return n - bestK;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int T = fs.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            int n = fs.nextInt();
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) arr[i] = fs.nextLong();
            sb.append(minOperations(arr)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 题意：最少相邻合并次数使所有数相等
// 方法：枚举“段和”为前缀和且整除总和的候选，利用哈希集合校验所有倍数是否为前缀和。

#include <bits/stdc++.h>
using namespace std;

long long min_operations(const vector<long long>& a) {
    int n = (int)a.size();
    long long S = 0, mx = 0;
    for (auto v : a) { S += v; mx = max(mx, v); }

    vector<long long> prefList;
    prefList.reserve(max(0, n - 1));
    unordered_set<long long> prefSet;
    prefSet.reserve(max(16, n * 2));

    long long pref = 0;
    for (int i = 0; i < n - 1; ++i) {
        pref += a[i];
        prefList.push_back(pref);
        prefSet.insert(pref);
    }

    sort(prefList.begin(), prefList.end());

    long long bestK = 1; // 合并为一段必可行
    for (auto x : prefList) {
        if (x < mx) continue;
        if (S % x != 0) continue;
        long long K = S / x;
        if (K > n) continue;

        bool ok = true;
        long long t = x;
        while (t < S) {
            if (!prefSet.count(t)) { ok = false; break; }
            t += x;
        }
        if (ok) {
            bestK = max(bestK, K);
            if (bestK == n) break;
        }
    }
    return n - bestK;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << min_operations(a) << "\n";
    }
    return 0;
}

题目内容

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

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

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

输入描述

第一行,包含一个正整数 $T(1 ≤T≤3)$ 代表测试数据的组数

对于每组测试数据,分别有两行:

第一行,仅有一个正整数 $n(1 ≤n≤ 10^5)$

第二行,包含 $n$ 个正整数,分别表示 $a_1,a_2,...,a_n(1≤a_i ≤ 10^9)$

输出描述

对每组测试，输出一个整数，表示使所有剩余数字相等所需的最少操作次数.

样例1

输入

2
4
2 3 3 2
4
10 9 8 7

输出

2
3

说明

对于第一组数据,可以在两次合并操作后,变为数组 $[5,5]$

对于第二组数据,可以在三次合并操作后,变为数组 $[34]$