AcWing 4366. 上课睡觉
好久没写题,一写就发现脑子生锈了(。
题目描述
有 \(N\) 堆石子,每堆的石子数量分别为 \(a_1,a_2,⋯,a_N\)。
你可以对石子堆进行合并操作,将两个相邻的石子堆合并为一个石子堆,例如,如果 \(a=[1,2,3,4,5]\),合并第 \(2,3\) 堆石子,则石子堆集合变为 \(a=[1,5,4,5]\)。
我们希望通过尽可能少的操作,使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。
本题一定有解,因为可以将所有石子堆合并为一堆。
题意
这道题我初步的理解是,要划分出若干个区间,其中每个区间都是连续的,并且每个区间的石子数量和相等,求最小的合并次数,也就是最多的区间数量。
大佬的翻译是这样的:
给你一个长度为 \(n\) 的数组 \(a\),相邻的两个元素可以合并成一个元素。设合并完每个元素都相等的数组 \(a′\) 长度为 \(n′\),求 \(\min \{n−n′\}\)。
解题思路
我一上来想到的就是暴力枚举,但是我的暴力比大佬们的要更简陋,因为缺少了进一步挖掘题意,并且没有根据数据范围作进一步的思考。
我的思路:
-
从左到右枚举。
-
首先枚举第一个区间,即固定第一个元素为左端点,枚举其右端点,之后即可每个区间的和\(S\),即每堆石子的个数。
-
上述右端点右边的元素即第二个区间的左端点,此时继续枚举,目的是找到合法右端点,使得区间和为\(S\)。
- 若找到,则依次类推继续第三个等;
- 若未找到,则更改第一个区间的右端点。
(由于元素非负,则这个区间和递增,若后续区间和达不到这个值,则可认为找不到)
-
处理特殊情况。。。
-
时间复杂度应该是O(N_2)
由于数据范围是\(10^5\),因此复杂度大概是\(\text{O}(n\log n)\),也就是说我的做法需要将一个维度优化至\(\log n\)。(也许可能得推翻重来)
优化的思路:
根据题意,由于合并之后每堆石子的个数都相同,设堆数为\(cnt\),则每堆的石子数则为\(S = \frac{sum}{cnt}\)。这个式子说明,\(S\) 是 \(sum\) 的因数。也就是说,没有必要以\(O(n)\)的复杂度枚举第一个区间的右端点来得到\(S\),而是枚举 \(sum\) 的因数,或者说用这个性质作为条件进行优化。具体如下:
- 从左到右枚举
- 枚举\(S\),可以是从\(1\)到\(n\),也可以像上面那个思路那样枚举右端点再计算
- 判断\(S\)是否为\(sum\)的因数,否,则继续枚举
- 依次判断能否合并为区间和为\(S\)的区间,直到最后
- 在过程当中统计一下合并次数
- 特殊情况
代码
// Problem: 上课睡觉
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4369/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int T, n;
int a[N], s[N];
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while(T -- ) {
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
int ans = 0, flag = 0, tepAns = 0;
for (int i = 1; i <= n; i ++ ) {
int sum = s[i] - s[0];
if (sum && s[n] % sum) continue; // 优化:sum 是所有石子数量之和的因数
tepAns = i - 1; // 第一堆石子的合并次数
int left = i + 1;
for (int right = left; right <= n; right ++ ) {
int tepSum = s[right] - s[left - 1];
if (tepSum == sum) { // 判断后续区间石子和是否等于 sum
if (right != left) tepAns += right - left;// 只有一个元素的区间不需要合并
left = right + 1;
right = left - 1;
continue;
}
if (tepSum > sum) { // 小优化,由于tepSum单增,大于sum就可以结束
break;
}
}
if (left == n + 1) {
ans = tepAns;
break;
}
}
cout << ans << endl;
}
return 0;
}
标签:上课,4366,int,sum,石子,枚举,端点,区间,AcWing
From: https://www.cnblogs.com/tsrigo/p/17031516.html