题目描述
有 N个石子堆成一堆。
你可以对石子堆进行拆分操作,具体为选中一堆现有石子堆,将其中的石子分为两堆(不能为空)。
此外,在任何时候,最小石子堆的石子数量都必须严格大于最大石子堆的石子数量的一半。
我们希望,通过将石子堆进行拆分,最终可以满足:
石子堆的总数量尽可能大,不妨设这个总数量的最大可能值为 M。
满足上一条要求的前提下,最大石子堆石子数量与最小石子堆石子数量之差尽可能小,不妨设这个差的最小可能值为 D。
请你计算并输出M和D的值。
输入格式
一个正整数 N。
输出格式
一行,输出M和D。
数据范围
2≤N≤200
思路
首先数据范围200,对于数据范围较小的题目,在没有合适的解法下,考虑爆搜枚举所有方案求出结果。
分析方案的合法性:
1:初始仅有一个堆,不妨设x+y==a且x<=y
分后得满足x>y/2,故合法方案的取值为y/2<x<=y
故满足条件a/3<x<=a/2的方案为合法方案
2:当有堆数n>=2,首先在考虑合法方案且满足条件1的分法下,分后的堆可能依旧为最大堆,也可能不是最大堆,故须考虑分前的最大堆和次大堆,不妨设分前最大堆为a,次大堆为b
1)当a==b,此时方案不合法,由条件1分后x<=a/2==b/2,不满足题意
2)当a!=b,分后需满足条件a/3<x<=a/2且x>b/2,故需满足 max(a/3,b/2)<x<=a/2
爆搜所有方案即可求解
算法
(DFS)
C++ 代码
/*
数据范围200,可以采用爆搜
*/
#include<iostream>
using namespace std;
const int N=210;
int n;
int w[N],cnt; //分后的石堆和数量
int m,d;
int getd()
{
int MAX=0,MIN=210;
for(int i=0;i<cnt;i++)
{
MAX=max(MAX,w[i]);
MIN=min(MIN,w[i]);
}
return MAX-MIN;
}
//爆搜所有方案
void DFS()
{
if(cnt>m) m=cnt,d=getd();
else if(cnt==m) d=min(d,getd());
if(cnt==1) //只有一个石堆的情况
{
int a=w[0];
for(int x=a/3+1;x<=a/2;x++)
{
w[0]=x,w[cnt++]=a-x;
DFS();
w[0]=a,cnt--; //恢复现场
}
}
else //不仅一堆的情况
{
int i=0,j=-1; //枚举出最大堆和次大堆
for(int k=1;k<cnt;k++)
{
if(w[k]>=w[i]) j=i,i=k; //大于最大堆
else if(j==-1||w[k]>w[j]) j=k; //大于次大堆
}
int a=w[i],b=w[j];
if(a!=b) // 最大堆与次大堆不相同才能继续
{
for(int x=max(a/3,b/2)+1;x<=a/2;x++)
{
w[i]=x,w[cnt++]=a-x;
DFS();
w[i]=a,cnt--; //恢复现场
}
}
}
}
int main()
{
cin>>n;
w[cnt++]=n;
DFS();
cout<<m<<' '<<d<<endl;
return 0;
}