荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
回复 wwwyhx
应该是不会漏,这个方法会尝试所有可能的情况。对任何一个可能的组合,总有一个升序的排法,那这个搜索的方法就应该能搜出来
darksteel 发表于 2011-5-12 13:21 ![]()
我给一个证明:
反证法:
假设下标为i时,存在第一个漏网之鱼(i之前的篮子都可以组合成 1到sum=a[0]+..a[i-1]的各个数),那么,也就是说在区间[sum+1,sum+a[i]]会漏掉一个,这个数不能由前i个篮子组合得到。
但不会漏掉,因为a[i]一定<=sum,如果漏掉了就和题设矛盾。
而a[i]一定不能大于sum,为什么?? 因为如果a[i]大于sum,那么(sum+1,sum+a[i])之间会漏掉无法弥补的数字, 因为a[i]后面的数只会比a[i]大 |
|