Sleeping in Class

题意

给定数组 a。一次操作可以合并两个相邻元素，合并后的值是它们的和。

求最少多少次操作，可以让最终数组中的所有元素相等。

思路

先看一个小数据 BFS 暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:36
 * update_at: 2026-07-11 17:37
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

bool all_equal(vector<int> state) {
    for (int i = 1; i < (int)state.size(); i++) {
        if (state[i] != state[0]) {
            return false;
        }
    }
    return true;
}

int bfs_solve(vector<int> start) {
    queue<vector<int> > q;
    map<vector<int>, int> dis;

    q.push(start);
    dis[start] = 0;

    while (!q.empty()) {
        vector<int> cur = q.front();
        q.pop();

        int d = dis[cur];
        if (all_equal(cur)) {
            return d;
        }

        int len = (int)cur.size();
        for (int i = 0; i + 1 < len; i++) {
            vector<int> nxt;
            for (int j = 0; j < len; j++) {
                if (j == i) {
                    nxt.push_back(cur[j] + cur[j + 1]);
                    j++;
                } else {
                    nxt.push_back(cur[j]);
                }
            }

            if (dis.find(nxt) == dis.end()) {
                dis[nxt] = d + 1;
                q.push(nxt);
            }
        }
    }

    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<int> a;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            a.push_back(x);
        }

        cout << bfs_solve(a) << '\n';
    }

    return 0;
}

这个暴力把当前数组看成状态，每一步枚举合并哪一对相邻元素。BFS 第一次到达“所有元素相等”的状态时，步数就是最少操作次数。

满分做法不枚举操作顺序，而是看最终留下多少段。

如果最终留下 r 个元素，那么合并次数就是：

text

1N - r

要让操作次数最少，就要让 r 尽量大。

合并不会改变总和。如果最终 r 个元素全相等，那么每个元素都必须是：

text

1total_sum / r

所以 r 必须整除 total_sum。

对于一个固定的 $target_sum = total_sum / r$ ，从左到右累加：

当前段和小于 target_sum，继续加；
当前段和等于 target_sum，切出一段；
当前段和大于 target_sum，这个 r 不可行。

从 $r = N$ 开始往下枚举，第一个可行的 r 最大，答案就是 N-r。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:36
 * update_at: 2026-07-11 17:37
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int a[MAXN];

bool can_split(int target_sum) {
    int cur_sum = 0;
    for (int i = 1; i <= n; i++) {
        cur_sum += a[i];
        if (cur_sum > target_sum) {
            return false;
        }
        if (cur_sum == target_sum) {
            cur_sum = 0;
        }
    }
    return cur_sum == 0;
}

void solve_case() {
    cin >> n;
    int total_sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        total_sum += a[i];
    }

    // r 表示最终保留的段数，越大需要合并的次数越少。
    for (int r = n; r >= 1; r--) {
        if (total_sum % r != 0) {
            continue;
        }
        int target_sum = total_sum / r;
        if (can_split(target_sum)) {
            cout << n - r << '\n';
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }

    return 0;
}

复杂度

设 d 是 total_sum 的因子数量。

时间复杂度为 $O(N \cdot d)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键转换是：最少合并次数等价于最大化最终段数。

最终每个数都是原数组的一段连续和，因此枚举段数并检查能否切成等和连续段即可。

目录

题意

思路

代码

复杂度

总结