合并成均匀的石子

acwing 4366

有 n 堆石子，你可以不断地合并相邻的两堆，请你求出使用最少合并次数，使得这个石子堆集合中的每堆数量相同。

例如有石子堆集合：[1, 2, 3, 1, 1, 1]，我只需要用 \(3\) 步就能合并成 [3, 3, 3]。

输入格式

第一行一个整数 t 代表测试样例的数量；

对于每一个测试样例，先输入一行一个整数 n 代表有 n 堆石子，再输入一行有 n 个整数，分别代表各堆石子的石子数量。

输出格式

输出 t 个整数，分别代表各个测试样例的答案。

数据范围

\(1 \leq\) t \(\leq 10\)

\(1 \leq\) n \(\leq 10 ^ 5\)

\(0 \leq\) a_i \(\leq 10 ^ 6\)

找规律、特点

先考虑最终结果，该石子堆集合一定会合并成 k 个元素，并且这些元素的值都为 res；

若我们假设 sum 为该石子堆集合的石子总数，那么 sum = k * res，所以 res 必定是 sum 的因子；

由于合并时只能从相邻的两堆开始合并，若要使得合并的次数最少，那么只需要 res 是满足条件的最小；

你可以假设如果不是满足条件的最小 res 可以使得结果「合并的次数」最少成立的话，我们假设合并次数为 ans，那么合并次数 ans 与 k、res 的关系为：

ans = sum - k = sum - sum / k = sum * (1 - 1/res)

所以，要使得 ans 最小，那么 res 就要尽可能的小。

求出所有的因子

时间复杂度为 \(\sqrt{n}\)

求出所有的因子

set<LL> fdi(LL n)
{
    set<LL> res;
    for (LL i = 1; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            res.insert(i); res.insert(n / i);
        }
    }
    return res;
}

因子个数

因子个数均摊为 \(log(n)\)，其中：

int 范围内最大的因子个数是 1600；

\(10 ^ 6\) 范围内的最大因子个数是 240，该数为 720720

因此，我们完全可以求出 sum 的所有因子，从最小的一一开始枚举，并从石子堆集合的开头处开始合并模拟看看该因子是否符合条件；

时间复杂度也高不到哪去：\(O(nlog(n))\)

代码参考

#include <iostream>
#include <set>

using namespace std;
typedef long long LL;
const int N = int (1e5 + 10);

LL t, n, a[N];

set<LL> fdi(LL n)
{
    set<LL> res;
    for (LL i = 1; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            res.insert(i); res.insert(n / i);
        }
    }
    return res;
}

void solve(void)
{
    cin >> t; 
    while (t --)
    {
        cin >> n;
        LL sum = 0;
        for (int i = 1; i <= n; i ++) cin >> a[i], sum += a[i];
        auto di = fdi(sum); di.insert(0); // 对 sum 为 0 特殊处理。

        for (auto x : di)
        {
            LL i = 1, k = 0, tmp = 0, on = 0;
            while (i <= n)
            {
                tmp += a[i];
                if (tmp == x)
                {
                    k ++, tmp = 0;
                    if (i == n) cout << n - k << endl, on = 1;
                }
                else if (tmp > x) break;

                i++;
            }
            if (on) break;
        }
    }
}

int main(void)
{
    solve();
    return 0;
}