当前位置：首页 > news >正文

4366. 上课睡觉

news 来源：原创 2024/5/16 6:58:44

Link

文章目录

4366. 上课睡觉
- 题意
- 思路
- 代码

4366. 上课睡觉

题意

有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。
你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。
我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。
本题一定有解，因为可以将所有石子堆合并为一堆。
思路

约数的二级结论：
- int范围内，最多的约数有1600个
- 720720，有240个约数
- 一个数的约数大约是 logn 个
先算出整个数组的总和sum，如果要分段，每一段的总和必须是sum的约数，那么就可以枚举sum的每个约数，看符合条件的哪个合成次数最少
枚举时，从左到右进行挨个枚举，每个数一次加入，如果大于了约数，肯定不成立；等于的话，就清0，继续往右扫

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-01 20:33:22
* @FilePath: \Acwing\4366\4366.cpp
* @LastEditTime: 2023-01-01 20:57:14
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

// #undef N
// const int N = 1e5 + 10;

#undef int

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int sum = accumulate(a.begin(), a.end(), 0);

    vector<int> b;
    for (int i = 1; i * i <= sum; ++i)
    {
        if (sum % i == 0)
        {
            b.push_back(i);
            if (i * i != sum)
                b.push_back(sum / i);
        }
    }
    if (!SZ(b))
    {
        cout << "0\n";
        return;
    }
    sort(b.begin(), b.end());

    auto fun = [&](int x) {
        int cnt = 0, tmp = 0, flag = 0;
        for (int i = 0; i < n; ++i)
        {
            if (flag)
                cnt++;
            tmp += a[i];
            flag = 1;
            if (tmp == x)
                tmp = 0, flag = 0;
            if (tmp > x)
                return INT_MAX;
        }
        return cnt;
    };

    int ans = INT_MAX;
    for (auto x : b)
    {
        ans = min(ans, fun(x));
    }
    cout << ans << '\n';
    return;
}

signed main()
{
    IOS;
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}