方是否录用.具体做法是,首先确定一个正整数k(1≤k≤n-1),然后对每位应聘者通过面谈打一个分数,打的分数都不相同.前k位都不录用,设前k位的最高得分为m.从第k+1位起,只要得分超过m就录用,不再考虑后面的人.如果n-k-1位的得分都不超过m,此时只剩下最后一位,不管他得多少分都录用.算法描述如下,其中srore(i)是第i位应聘者的得分。
On-Line Max(n,k)
1.m←-∞
2.for i←1 to k do
3.if score(i)>m then m←scere(i)
4.for i←k+1 to n-1 do
5.if score(i)>m then return i
6.return n
假设n位应聘者的排列服从均匀分布,