思考题1.4

P56. Q1.赛跑问题( GS )。假定有25名短跑选手比赛争夺前三名，赛场上有五条赛道，一次可以有五名选手同时比赛。比赛并不计时，只看相应的名次。假设选手的发挥是稳定的，也就是说如果约翰比张三跑得快，张三比凯利跑得快，约翰一定比凯利跑得快。最少需要几次比赛才能决出前三名？

答：

  • 首先需要5次。25人分为5组，每组比赛一次，所有选手比赛一次需要比赛5次
  • 然后增加1次
    • 每组第一名再比赛一次，可以找出第一名，假设为A1,B1,C1,D1,E1，同时考虑无用功，后两名选手D1,E1已经失去了争夺前三名的机会
    • 第二名候选人有两个选手A2,B1（即前5次同一组比赛中仅次于第一名的选手和第6次比赛仅次于第一名的选手）
    • 第三名候选人有三个选手A3,B2,C1（除去第六次比赛中淘汰的两名选手其他所在组的第一名）
  • 第二名和第三名的候选人一共为5人，需要再比赛一次
  • 总计至少需要7次

本题可转化为求"N个排序数组中的前K个最小值"。

P57. Q2.区间排序。如果有N个区间[l1,r1],[l2,r2],…,[lN,rN]，只要满足下面的条件我们就说这些区间是有序的：存在xi∈[li,ri]，其中i=1,2,…,N。 比如，[1, 4]、[2, 3]和[1.5, 2.5]是有序的，因为我们可以从这三个区间中选择1.1、2.1和2.2三个数。同时[2, 3]、[1, 4]和[1.5, 2.5]也是有序的，因为我们可以选择2.1、2.2和2.4。 但是[1, 2]、[2.7, 3.5]和[1.5, 2.5]不是有序的。 对于任意一组区间，如何将它们进行排序？

答：题目有序的含义可解读为： 当 \(\exists x i \in[l i, r i], x j \in[l j, r j]\) ，使得 \(x i<x j\) ，称 \([l i, r i] 、[l j, r j]\) 是有序的。

首先考虑两个区间A \([l_1,r_1]\)和 B \([l_2,r_2]\)的情况。

  • B在A的右方，\(l_1 < r_1 < l_2 <r_2\),有序
  • B在A的左方，\(l_2 < r_2 < l_1 < r_1\),无序
  • AB有重叠
    • \(l_2 < l_1 < r_2 < r_1\)，有序
    • \(l_2 < l_1 < r_1 < r_2\)，有序
    • \(l_1 < l_2 < r_2 < r_1\)，有序
    • \(l_1 < r_1 < l_2 < r_2\)，有序

第二种情况时是无序的。