Q2_赛马排名.java

package com.algorithm.demo.iq;

/**
 * 25匹马，5个跑道，每个跑道最多能有1匹马进行比赛，最少比多少次能比出前3名？前5名？
 * 链接：https://www.nowcoder.com/questionTerminal/ea2cf19557d546819d7fde300daeabb1
 * 来源：牛客网
 * <p>
 * (1)求前3名要7次；
 * 将马分成A、B、C、D、E五组。
 * 第1-5次比赛：各组分别进行比赛，决出各组名次,取每组前三名
 * A1、A2、A3，
 * B1、B2、B3，
 * C1、C2、C3，
 * D1、D2、D3，
 * E1、E2、E3。
 * 第6次比赛：A1、B1、C1、D1、E1，
 * 假设得到的结果是A1、B1、C1、D1、E1，A1是跑的最快的，那么分析A组A2、A3还有希望冲进前3，B组呢？只有B2还有希望冲进前3，C组的C1，C2并没有希望冲进前3了，因为C1是比赛的名次是第3名了，D组E组都没有希望了。现在已经知道A1肯定是第一名，剩下A2、A3、B1、B2、C1是有希望冲进前三的。
 * 第7次比赛：A2、A3、B1、B2、C1比赛求出第2，第3即可。
 * (2)求前5名：
 * 将马分成A、B、C、D、E五组。
 * 第1-5次比赛：各组分别进行比赛，决出各组名次
 * A1、A2、A3、A4、A5，
 * B1、B2、B3、B4、B5，
 * 。。。。
 * 。。。。。。E4、E5。
 * 第6次比赛：A1、B1、C1、D1、E1，
 * 第一名是跑的最快的。
 * 第7次比赛：将上次第一名所在组的下一号马再和剩余的4匹1号马比赛，
 * 第一名是跑的第二快的马，由于只有4个名额，所以跑的最慢的马和所在组剩余的马全部被淘汰。
 * 第8次比赛：将上次第一名所在组的下一号马、上次第二名所在组的下一号马和剩余的3匹马比赛，
 * 第一名是跑的第三快的马，由于只有3个名额，所以跑的最慢的两匹马和所在组剩余的马全部被淘汰。
 * 在剩下的比赛中分别淘汰慢的，将排名稍后的加进来比赛，最多跑到第10次就可以选出最快的5匹马。如果在某一次比赛中排名前几的是同一组的且和已经选出的马加一起大于等于5，就可以提前决出前5名。
 * 所以8-10次就可以选出最快的5匹马。
 */
public class Q2_赛马排名 {
}