讨论 / 此问题会有多解
atttx123 2012-01-08 03:49:00
点我顶贴 收藏 删除
当N=13时,钱袋数为4,

有两种方法:

1, 2, 3, 7

1, 2, 4, 6

均符合题目要求。

#1 EBC5@2008-11-04 22:08:00
回复 删除
没考虑,直接做的,就AC了

#2 atttx123@2008-11-04 23:35:00
回复 删除
人工置顶
#3 jww521@2009-08-24 18:05:00
回复 删除
是的,的确有多解,

当N=5时 布袋数为3

eg1: 1 1 3 可以

eg2: 1 2 2 也可以。

#4 quicksort@2010-07-13 01:07:00
回复 删除
回复 1楼

嗯嗯,我利用二进制做的就差了一个点。

测试结果错误.错误结果为:3

1 2 2

正确结果应为:3

1 1 3

#5 noip2012@2010-12-31 04:08:00
回复 删除
确实有多解
#6 怡红公子@2011-12-13 07:14:00
回复 删除
自己胡乱做的,竟AC了!

#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;

}

#7 怡红公子@2011-12-13 07:18:00
回复 删除
回复 板凳atttx123 的帖子

题目要求:他想方设法使自己在满足上述要求的前提下,所用的钱袋数最少,并且不有两个钱袋装有相同的大于1的金币数

#8 怡红公子@2011-12-13 07:26:00
回复 删除
回复 楼主atttx123 的帖子

明显,按照二进制算是最优的;

比如:

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

算算总共取了多少钱袋,对比一下吧!

#9 怡红公子@2012-01-08 03:49:00
回复 删除
抱歉

看样子不是

#10 飞厦yzm@2014-11-15 19:05:21
回复 删除
回复 #3 jww521:有多解是对的,但您的数据不对,题目规定没有两个钱袋里的钱数相同
查看更多回复
提交回复