嗯嗯,我利用二进制做的就差了一个点。
测试结果错误.错误结果为:3
1 2 2
正确结果应为:3
1 1 3
#include<iostream>
using namespace std;
int main()
{
int m,i,sum=0;long long s=1;
cin>>m;
while(m>=s)
{
m=m-s;
s=s*2;
sum++;
}
if(m!=0&&m%2==0)
{
cout<<sum+m-1<<endl;
for(i=1;i<m;i++) cout<<1<<" ";
for(i=1;i<=s/4;i=i*2)
cout<<i<<" ";
cout<<s/2+1;
}
else
{
if(s/2<m)
{sum++;cout<<sum<<endl;
for(i=1;i<=s/2;i=i*2)
cout<<i<<" ";
cout<<m;system("pause");
return 0; }
cout<<sum<<endl;
for(i=1;i<=s/4;i=i*2)
cout<<i<<" ";
cout<<s/2;
}
system("pause");
return 0;
}
题目要求:他想方设法使自己在满足上述要求的前提下,所用的钱袋数最少,并且不有两个钱袋装有相同的大于1的金币数
明显,按照二进制算是最优的;
比如:
1, 2, 3, 7
当所需1时,只需取:1
当所需2时,只需取:2
当所需3时,只需取:3
当所需4时,只需取:1,3
当所需5时,只需取:2,3
当所需6时,只需取:1,2,3
当所需7时,只需取:7
当所需8时,只需取:1,7
当所需9时,只需取:2,7
当所需10时,只需取:3,7
当所需11时,只需取:1,3,7
当所需12时,只需取:2,3,7
当所需13时,只需取,1,2,3,7
1, 2, 4, 6
当所需1时,只需取:1
当所需2时,只需取:2
当所需3时,只需取:1,2
当所需4时,只需取:4
当所需5时,只需取:1,4
当所需6时,只需取:2,4
当所需7时,只需取:1,6
当所需8时,只需取:2,6
当所需9时,只需取:1,2,6
当所需10时,只需取:4,6
当所需11时,只需取:1,4,6
当所需12时,只需取:2,4,6
当所需13时,只需取:1,2,4,6
算算总共取了多少钱袋,对比一下吧!