【AcWing每日一题】4366. 上课睡觉
有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。
你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。
我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。
本题一定有解，因为可以将所有石子堆合并为一堆。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 N。
第二行包含 N 个整数 a1,a2,…,aN。
输出格式
每组数据输出一行结果。
数据范围
1≤T≤10,
1≤N≤105,
0≤ai≤106,
∑ai≤106,
每个输入所有 N 之和不超过 105。
自己的解法：
- 用堆排序的方法，对于每一组数据，建立初始小根堆，进行堆排序。
- 每次排好一个元素后，进行对已排序序列检查，如果已经完成堆排序的序列的部分和（从前往后）可以大于等于目前的最大值，则合并这部分。（全是0的情况除外）
- 合并后更新下次排序需要的参数，继续进行堆排序，合并。
- 直至所有的数都一样或者合成一堆，算法停止，输出答案，进行下一组的堆排序。
- 这需要每次合并后都检查是否每个数都一样。
- 因为考虑到数据量的问题，用枚举是O(n2)的复杂度，会超时，用堆排序降到O(nlog2n)的复杂度。
我的推导过程：
但是考虑到如果每次排序后都进行检查，那么时间复杂度也会上升到O(n2)
自己的代码（没写完）：
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> > v; //v存放所有的数组
int max_vj = -0xffff; //每组数据的最大值
int res = 0;
//小根堆的建立
void HeapAdjust(vector<int> &A, int k, int len){
int t = A[k]; //暂存这个分支结点
for(int i = 2*k; i <= len; i *= 2){ //从这个分支结点开始向下调整
if(i < len && A[i] > A[i+1]) i++; //右孩子更小
if(t <= A[i]) break; //分支结点已是子堆中的最小值，符合特性
else{ //不符合特性，需要调整
A[k] = A[i]; //换的时候只是覆盖
k = i; //下标要交换，下次还说与A[0]比较
}
}
A[k] = t; //放到最终符合特性的位置上
}
void BuildMinHeap(vector<int> &A, int len){
//从最后一个分支结点开始，逐级向上建堆
for(int i = len/2; i > 0; i--)
HeapAdjust(A, i, len);
}
//堆排序
void HeapSort(vector<int> &A, int len){
for(int i = len; i > 1; i--){ //n-1趟交换和建堆过程
swap(A[i], A[1]); //堆顶元素和堆底元素互换
//交换后检查是否符合合并的条件
//如果已经完成堆排序的序列的部分和（从后往前）可以大于等于目前的最大值，则合并这部分
//合并后更新下一次需要的参数
if(){
A[len-1] = A[len]+A[len-1]; //合并
if(A[len-1] > max_vj) max_vj = A[len-1]; //更新最大值、长度、合并次数
A[0]--; len--; res++;
}
HeapAdjust(A, 1, i-1); //将剩余的元素调整
}
}
int main(){
int T, N, an; //T组测试数据，每组数据包含N个整数an
cin >> T; //测试数据的数量
vector<int> vj; //每组数据存放的数组
//下面搞定输入
for(int i = 0; i < T; i++){
cin >> N; //N个整数
vj.clear(); //对数组先清空
vj.push_back(N); //每个数组的第一个位置存放这个数组的长度
for(int j = 0; j < N; j++){
cin >> an; //输入a1~an
vj.push_back(an);
}
v.push_back(vj);//将每组数据放入v
}
for(int i = 0; i < T; i++){
vector<int> vj = v[i];
if(vj[0] == 2 && vj[1] != vj[2]){ //如果只有两个数且不相等
cout << 1 << endl;
continue;
}else if(vj[0] == 1){ //如果只有一个数
cout << 0 << endl;
continue;
}
//找出每组数据的最大值
for(int j = 1; j <= vj[0]; j++)
if(vj[j] > max_vj) max_vj = vj[j];
//对于每组数据建立初始的小根堆
BuildMinHeap(vj, vj[0]); //建堆
HeapSort(vj, vj[0]); //堆排序的同时合并
cout << res << endl;
max_vj = -0xffff; //重置
res = 0;
//测试堆排序结果
// for(int i = 1; i <= vj[0]; i++) cout << vj[i] << " ";
// cout << endl;
// cout << max_vj << endl;
}
return 0;
}
y总的方法：
他的方法是用的数论的推导
总的石子个数sum，最终每堆石子cnt个，cnt只有整除sum才可以
cnt的数量等于sum的约数个数，平均每个数的约数个数是O(logn)个
106以内，约数个数最多的数是720720，有240个约数
int范围内，约数个数最多的数有1600个
- 知道了这个前提，我们就可以用枚举的方法，枚举所有的约数，找到可以取到的并整除sum的数
- 在所有的数里面找到合并次数最少的方案
- 我们知道，最终合并后有sum/cnt堆石子，原来有n堆
- 所以合并的次数为 n-sum/cnt
- 我们只需要找到一个最小的符合条件的cnt
- 所以我们只需要从小到大枚举cnt，看是否成立就可以了
一开始还有一个条件我没注意到，只能合并相邻的两堆，这样堆排序好像没法用了
那我们如何判断cnt是否成立？（能否将每一堆的数量变成cnt）
- 对于每个cnt，我们对原始序列从前向后枚举
- 如果当前堆的石子数量大于cnt，那一定无解，枚举下一个cnt
- 如果当前堆的石子数量等于cnt，如果后面的数量是0，可以加到前面或后面的一堆；如果不是0，那就合并到下一段
- 根据计算，大约240个约数，最多用107次计算量，可以在规定的时间内完成
最后附一下代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int w[N];
//判断当前的约数是否符合条件
bool check(int cnt)
{
//从前向后枚举序列的每一段
for (int i = 0, s = 0; i < n; i ++ )
{
s += w[i]; //合并相邻的两段
if (s > cnt) return false; //如果合并后的石子数量大于cnt，无解
if (s == cnt) s = 0; //如果等于这个约数cnt，继续合并后面的段
}
return true;
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n); //石子的堆数
int sum = 0; //石子的总数sum
for (int i = 0; i < n; i ++ ) //输入每堆石子个数
{
scanf("%d", &w[i]);
sum += w[i]; //计入到总数sum
}
for (int i = n; i; i -- ) //对于每堆石子，枚举寻找符合条件的cnt
if (sum % i == 0 && check(sum / i))//如果cnt能够整除sum，并且操作次数最小，且有解
{
printf("%d\n", n - i); //输出答案
break;
}
}
return 0;
}
//作者：yxc
//链接：https://www.acwing.com/activity/content/code/content/5027948/
//来源：AcWing
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。