如何在1到N个人当中找出明星？
两个条件：
1.有1到N共N个人，且提供一个函数reg（i,j）表示如果i认识j，则返回true，如果不认识返回false，注意这里i认识j并不一定代表j认识i，即不具有对称性
2.明星被其余的N-1个人认识，但是他不认识N-1个人当中的任何一个。
给定这两个条件，用O（N）的算法找出N个人当中的明星
lulu命
12 years, 10 months ago
Answers
这个问题等价于找未知序列数中的最小数
我们将reg这个函数等价为以下过程：
如果i认识j，记作i大于等于j,同样j不一定大于等于i,满足要求
i不认识j记作i<j
对明星k,他不认识所有人，则k是其中最小的数，且满足其余的人都认识他，也就是其余的人都大于等于k.
这样问题就被转换了。
就拿N=5来说
首先有数组S[5]={A,B,C,D,E}这5个变量，里边存放着随机数，求是否存在唯一最小数，如果存在位置在S中的哪里。（楼主这里是这个意思，按我的理解题中这个最小数一定是存在且唯一的）
int finds(S,N)
{
int flag=0;//用于判定是否有明星，即当前最小数另外出现几次
int temp=0;//存放最小数在S中的位置
for(i=1;i<N;i++)
｛
if(!reg(S[i],S[temp])//如果temp标号的数小于i标号的数
｛
temp=i;
flag=0;//更换怀疑对象（最小数）时，标记清零
｝
elseif(reg(S[temp]，S[i])//如果temp里存放的确实是唯一最小数是不会跑进这里来的
{
flag++;
` }
｝
if(flag>0) return -1;//表示没有明星,例如所有的数都相等
return temp;//返回明星在S中的位置
}
warlock
answered 12 years, 10 months ago