发信人: showcraft(Fortress Besieged), 信区: Algorithm
标 题: yc一道水题的优化
发信站: 饮水思源 (2013年03月24日00:17:03 星期天)
http://www.douban.com/note/268014824/
有一群海盗（不多于20人），在船上比拼酒量。过程如下：打开一瓶酒，所有在场的人平
分喝下，有几个人倒下了。再打开一瓶酒平分，又有倒下的，再次重复...... 直到开了第
4瓶酒，坐着的已经所剩无几，海盗船长也在其中。当第4瓶酒平分喝下后，大家都倒下了
。等船长醒来，发现海盗船搁浅了。他在航海日志中写到：“......昨天，我正好喝了一
瓶.......奉劝大家，开船不喝酒，喝酒别开船......”
请你根据这些信息，推断开始有多少人，每一轮喝下来还剩多少人。
如果有多个可能的答案，请列出所有答案，每个答案占一行。
格式是：人数,人数,...
例如,有一种可能是：20,5,4,2,0。
我的思路：
本质上本题等价于
1/a+1/b+1/c+1/d == 1
20>=a>b>c>d>0
求所有可能的{a,b,c,d}，其中a为初始人数，b为第一轮所剩人数，c为第二轮所剩人数，
d为第三路所剩人数。
多重算法的高效诀窍在于将遍历层次越少的循环放在越外层。对d估值，有1<d<4，即只能
取2或者3。
具体代码的话，d，b，c，a从外层到内层依次递增循环，令f=1/a+1/b+1/c+1/d，试探f是
否等于1，事实上质数可以直接跳过。对外层循环值固定的最内层，该层循环产生的可能结
果序列值为递减序列。因而一旦发现该层循环遍历产生的结果比1小，那就可以break，跳
出该层循环。
由此可以产生一个优化的技巧：
记录最内层break时的位置。比如说，对于最内两层，在b=b1层循环时，发现最内层a=a1时
f1<1，那么有a=a1-1时f2>=1，记x=f2-1<f2-f1=1/(a1-1)-1/a1=1/a1(a1-1)。
break之后b自加1，b=b1+1，此时d，c值固定，不考虑a，相比原来b部分减小的值记为
y=1/b-1/(b+1)=1/b(b+1)
如果b=a1-1，则x=y，事实上这种情况a1=b+1，如果f<1，无需继续遍历b，break跳出b循环
，返回到c层，c自加1继续循环遍历。
如果b<a1-1，则x<y，那么此时再遍历到a1-1就没有意义，顶多遍历到a1-2即可。
于是有a1-2>=b+2，a1>=b+4，只有在这种情况下才有必要b自加1继续遍历该层。其他情况
下，即如果b<a1<b+4，break，跳出b层循环。事实上对于非最内层的循环也可以类似递归
考虑，只是非最内层依次遍历产生的序列是一段段的递减序列拼合而成，情况会更加复杂
些，在此暂不做更深入的优化探讨了。
具体代码我就不写了，按照这种思路，应该能进行比较高效的优化。
--
豆瓣http://www.douban.com/people/knowcraft
博客http://www.yantan.cc/blog/?12226
微博http://weibo.com/u/1862276280
http://bbs.sjtu.edu.cn/file/Literature/1241706509292780.jpg
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 180.152.211.30]
※ 修改:·showcraft 于 2013年03月24日00:40:55 修改本文·[FROM: 180.152.211.30]
标 题: yc一道水题的优化
发信站: 饮水思源 (2013年03月24日00:17:03 星期天)
http://www.douban.com/note/268014824/
有一群海盗（不多于20人），在船上比拼酒量。过程如下：打开一瓶酒，所有在场的人平
分喝下，有几个人倒下了。再打开一瓶酒平分，又有倒下的，再次重复...... 直到开了第
4瓶酒，坐着的已经所剩无几，海盗船长也在其中。当第4瓶酒平分喝下后，大家都倒下了
。等船长醒来，发现海盗船搁浅了。他在航海日志中写到：“......昨天，我正好喝了一
瓶.......奉劝大家，开船不喝酒，喝酒别开船......”
请你根据这些信息，推断开始有多少人，每一轮喝下来还剩多少人。
如果有多个可能的答案，请列出所有答案，每个答案占一行。
格式是：人数,人数,...
例如,有一种可能是：20,5,4,2,0。
我的思路：
本质上本题等价于
1/a+1/b+1/c+1/d == 1
20>=a>b>c>d>0
求所有可能的{a,b,c,d}，其中a为初始人数，b为第一轮所剩人数，c为第二轮所剩人数，
d为第三路所剩人数。
多重算法的高效诀窍在于将遍历层次越少的循环放在越外层。对d估值，有1<d<4，即只能
取2或者3。
具体代码的话，d，b，c，a从外层到内层依次递增循环，令f=1/a+1/b+1/c+1/d，试探f是
否等于1，事实上质数可以直接跳过。对外层循环值固定的最内层，该层循环产生的可能结
果序列值为递减序列。因而一旦发现该层循环遍历产生的结果比1小，那就可以break，跳
出该层循环。
由此可以产生一个优化的技巧：
记录最内层break时的位置。比如说，对于最内两层，在b=b1层循环时，发现最内层a=a1时
f1<1，那么有a=a1-1时f2>=1，记x=f2-1<f2-f1=1/(a1-1)-1/a1=1/a1(a1-1)。
break之后b自加1，b=b1+1，此时d，c值固定，不考虑a，相比原来b部分减小的值记为
y=1/b-1/(b+1)=1/b(b+1)
如果b=a1-1，则x=y，事实上这种情况a1=b+1，如果f<1，无需继续遍历b，break跳出b循环
，返回到c层，c自加1继续循环遍历。
如果b<a1-1，则x<y，那么此时再遍历到a1-1就没有意义，顶多遍历到a1-2即可。
于是有a1-2>=b+2，a1>=b+4，只有在这种情况下才有必要b自加1继续遍历该层。其他情况
下，即如果b<a1<b+4，break，跳出b层循环。事实上对于非最内层的循环也可以类似递归
考虑，只是非最内层依次遍历产生的序列是一段段的递减序列拼合而成，情况会更加复杂
些，在此暂不做更深入的优化探讨了。
具体代码我就不写了，按照这种思路，应该能进行比较高效的优化。
--
豆瓣http://www.douban.com/people/knowcraft
博客http://www.yantan.cc/blog/?12226
微博http://weibo.com/u/1862276280
http://bbs.sjtu.edu.cn/file/Literature/1241706509292780.jpg
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 180.152.211.30]
※ 修改:·showcraft 于 2013年03月24日00:40:55 修改本文·[FROM: 180.152.211.30]
No comments:
Post a Comment