题目描述
有N堆石子,每堆石子上有a[i]个石子,每次合并只相邻两堆;
问合并多少次,使得合并后的每堆石子数量都相同。
解题思路
(1)假设最少的操作数为$x$(开始共有N堆),则最终的石子堆的个数为$N-x$;
(2)sum%i==0&&check(sum/i)
的理解
i:表示堆数 i = N-x;
sum/i:表示每堆个数
由于题意要让合并后的每堆石子都相同!!!(大前提)
所以i和sum/i都需要是sum的因子
对于题意,如果最后无法合并到每堆石子都相同,则会最后合并到只有一堆石子;
情况如下:
2 2 3
-> 2 5
-> 7
算法1
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int w[N];
int T,n;
bool check(int cnt)
{
for(int i = 0,s = 0;i<n;i++)
{
s += w[i];
if(s>cnt) return false;
else if(s==cnt) s = 0;
}
return true;
}
int main()
{
//input
cin>>T;
//processing
while(T--)
{
cin>>n;
int sum = 0;
//caculate the total of stone
for(int i = 0;i<n;i++)
{
cin>>w[i];
sum += w[i];
}
//check
for(int i = n;i>0;i--)
{
if(sum%i==0&&check(sum/i))
{
printf("%d\n",n-i);
break;
}
}
}
return 0;
}