有n个人，其中超过半数是好人，剩下的是坏人
好人只说真话，坏人可能说真话也可能说假话
这n个人互相都知道对方是好人还是坏人

现在要你从这n个人当中找出一个好人来，只能通过以下方式：
每次挑出两个人，让这两个人互相说出对方的身份，
你根具两个人的话进行判断。

问通过何种方法才能最快的找出一个好人来,
(要考虑最坏的情况)

            }
            else
            {
                sameNum--;
                i++;
                if(sameNum == 0)
                {
                   samePos = -1;
                }
    
           }
                continue;  
        }
        
        if(第i个人和第i + 1个人都说对方是好人)
        {
           
               samePos = i;
               sameNum = 2;
        }
       else
       {
           i += 2;
       }
   }

    最后要吗剩下一个好人,要吗剩下一串好人,复杂度为o(n) ,最快n/2,最慢n.写的不太严密,请大家指正.

楼上（天涯客）的可能没有看清楚要找出好人的要求。如果A是外人的话，那么你的评选还要继续下去。

1)对于编号为1,2,...,n的n个人,分别按(1,2),(3,4)...这样配对(当n为奇数时有一人剩余,此人暂放一边),然后选出所有同时说对方是好人的配对。

2)若没有这样的配对.则那么由于超过一半为好人,此时所有配对均为好人与坏人配对.进而n必为奇数,且刚才配对时剩下的那个人必为好人.完毕

3)若至少有一个这样的配对,则从所有这样的配对中各抽出一个人,连同刚才可能剩下的那个人,重新组成序列 1,2,...,m(m<=ceil(n/2)).在这个新序列中超过一半为好人.则对此序列重新跳到步骤1)进行筛选

以上算法最快为O(1),最慢为O(log n)

第二步：
ai和bi 互相说出对方的身份。i=1,..,n
如果ai和bi凳子上的人，说的不一样 和 都说对方是坏人的，两个人就搬凳子走人。（给我消失！）留ai和bi都说对方是好人的。
因为好人比坏人多，所以：如果都走人了，那最先开始站一边的就是答案。
                                   如果有剩下的人则：ai和bi凳子上的人，要么都是好人，要么都是坏人。
然后a组剩下的人中，第一个人坐最后一个人的凳子，最后一个人坐倒数第二个人的凳子，然后依次往前，第二个人坐第一个位置。
b组不动

第三步：
重复第二步
直到没有减人，则剩下的都是好人，随便找一个就是答案

改进的方法是在第二步最后加以个随即排序,但要保持ai 和bi相对的人始终相对，比如
上面情况随机以后变成：
   1   2   3   4   5   6   7   8   9  10   11 12  13  14  15   （新）
   4   2   7   8  10  11  15   3   9   1   5  12  13   6  14   （旧）
a  #   @   #   #   @   @   @   #   #   @   #   @   @   #   @
b  #   @   #   #   @   @   @   #   #   @   #   @   @   #   @