AcWing 4366. 上课睡觉
原题链接
简单
作者:
MyPower
,
2022-12-28 23:00:19
,
所有人可见
,
阅读 145
目的:求让每堆石子的个数(w[N])相同时操作数最小的数量
注:相邻的石子才可以合并
思想:(n - sum / cnt )最小 //cnt是每堆石子的数量
枚举
1.如果全部石子的和sum % 堆数 = 0 。//意味可能存在操作后使每堆石子数量相同的情况
2.在 1 的情况下,如果 1~n s > cnt //意味着该种情况
s = cnt //继续找 =》 s = 0,直到所有s = cnt;
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int w[N];
int n;
bool check(int cnt)
{
for(int i = 1, s = 0; i <= n; i++)
{
s += w[i];
if(s > cnt)return false;
if(s == cnt) s = 0;
}
return true;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int sum = 0;
scanf("%d",&n);//有n堆
for(int i = 1; i <= n; i++)
{
scanf("%d",&w[i]);
sum += w[i];//计算全部石子数量
}
for(int i = n ; i > 0; i--)
{
if(sum % i == 0 && check(sum / i))
{
printf("%d",n - i );
puts("");
break;
}
}
}
return 0;
}