请问这个问题的算法如何优化

1000个人，分两种：好人坏人。里面最少有501个是好人。
如果抽出来两个人，那么好人会说出另外一个人到底是好人还是坏人，而坏人的答案是不确定的。（类似于真话假话）
现在要用一个算法，找出一个一定是好人的人

最简单的方法：
那一个人出来和所有人放一起
如果超过501个人说他是好的，那他一定是好的，否则一定是坏的
这样的方法是可行的，但是复杂度是n方

要求要优化到n
想了半天都没想出来了，请高手支招

问题的关键是：一定要考虑最差情况。

评论

6 楼 cash-007 2007-12-12  

想明白了，真是太厉害了！！！

5 楼 fengzl 2007-10-18  

不错受教了，才思敏捷阿

4 楼 lixiao 2007-10-18  

谢谢eastsun
最近比较忙～
那天看了你的思路，觉得确实厉害～
而且居然马上写了个程序。。呵呵～厉害的～～
今天刚把程序仔细又研究了一遍，跑上来再次感谢～

3 楼 jasongreen 2007-10-16  

强人。。强

(i)A中的人数是奇数,此时可以证明A中的好人比坏人多
(ii)A中的人数是偶数,将第一个人加进来,可以证明这个队的好人比坏人多.

这个证明过程很重要，思路的关键

2 楼 Eastsun 2007-10-10  

写了个代码演示:

import java.util.Random;
import java.util.Collections;
import java.util.Arrays;
import java.util.List;
/**
   演示代码
   @author Eastsun
   @version 1.0 2007/10/10
*/

public class GoodORBad{
    public static void main(String[] args){
        Man[] mans =new Man[5000];
        mans[0] =new Man(true);
        mans[1] =new Man(true);
        for(int index =2;index<mans.length;index++) mans[index] =new Man(index%2==0);
        List<Man> list =Arrays.asList(mans);
        //将mans的顺序打乱
        Collections.shuffle(list);
        
        Man m =choiceAGoodMan(mans);
        m.say();
    }
    /**
       从mans中选出一个好人,注意此方法将修改数组mans
    */
    public static Man choiceAGoodMan(Man[] mans){
        int remainder =mans.length;
        while(remainder>2){
            int i =0,j =0;
            while(i+1<remainder){
                Man a =mans[i], b=mans[i+1];
                i += 2;
                if(a.isGood(b)&&b.isGood(a)){ 
                    mans[j++] =a;
                }
            }
            if(i<remainder&&j%2==0){
                mans[j++] =mans[i];
            }
            remainder =j;
        }
        return mans[0];
    }
}

class Man{
    private static Random R =new Random();
    private boolean isGood;
    
    /**
      构造一个好人或坏人
    */
    public Man(boolean isGood){
        this.isGood =isGood;
    }
    /**
      判断other是否好人
      如果本身是坏人,就信口胡说
    */
    public boolean isGood(Man other){
        if(isGood) return other.isGood;
        else       return R.nextInt(2) ==0;
    }
    /**
      自己揭开面纱
    */
    public void say(){
        System.out.println(isGood?"Hey,I'm a good man!":"Hey,I'm a bad man!");
    }
}

1 楼 Eastsun 2007-10-10  

有点意思,貌似在<算法导论>上见过..
下面考虑一般的情况:
n个人,超过[n/2]的人是好人,从中找出一个好人
(1) n =1,2时全是好人
(2) n =2*m +1 时:
    将第一个晾在一边,剩下的两两配成m对
    对(a,b)两人互相提问,若至少有一人说对方是坏人,则其中至少有一个是坏人.若两人都说对方是好人,则两人要么全是坏人,要么全是好人.从后一种配对中每个挑出一个来组成一个队A
    (i)A中的人数是奇数,此时可以证明A中的好人比坏人多
    (ii)A中的人数是偶数,将第一个人加进来,可以证明这个队的好人比坏人多.
  总之,我们可以得到一个新的队,其人数<=m+1,且性质不变(好人比坏人多)
(3)n =2*m 和(2)差不多,更简单,略之

这样:我们在O(n)时间内把问题缩小到原规模的1/2

......
如此,在O(n)时间内可以解决问题.