1000个人，分两种：好人坏人。里面最少有501个是好人。
如果抽出来两个人，那么好人会说出另外一个人到底是好人还是坏人，而坏人的答案是不确定的。（类似于真话假话）
现在要用一个算法，找出一个一定是好人的人
最简单的方法：
那一个人出来和所有人放一起
如果超过501个人说他是好的，那他一定是好的，否则一定是坏的
这样的方法是可行的，但是复杂度是n方
要求要优化到n
想了半天都没想出来了，请高手支招
问题的关键是：一定要考虑最差情况。
题目：
有25匹马，一个5道的赛马场，最少比赛几次，能把这25匹马中的1，2，3名找出来，并排出1，2，3名？如何组织每次比赛？
马可以重复赛，不考虑疲倦影响速度等其他问题。
思路：
首先肯定，25匹要分组赛。
最容易掉入，也最容易识别的陷阱就是：
5匹一组，赛5次，然后每组第一名再赛一次，总共六次，就ok了。这样的问题就在于又可能某组的第二名比其他4组的第一名都快。进而想到最坏的 可能就是，分组的时候把真正的前三名分到同一组了。
问题的关键变成了第6次以后应该怎么挑选再赛的马
5分钟左右，应该就能想到下面的正确思路。
前6次就按照刚才的赛法，5次小组赛，一次各小 ...
评论排行榜