Powered by:NEFU AB-IN
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 intvoid 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; }