面试题 无平局单循环球赛 转载

n进m的无平局循环赛

n支球队打循环赛，前m支球队出线。每场比赛皆有胜负，没有平局。问一支球队最少赢多少场可能出线？最少赢多少场一定出线？

这个问题与百度的面试题有类似之处。为了方便叙述，我们定义几个符号。假设A表示参与循环赛的一些球队的集合，A1代表A中的第一名球队，A0代表A中的最后一名球队，那么：
w(A) : A中所有球队获胜场次的总和。
w(A1) : A中获胜场次最多的球队所获胜的场次数。
l(A) : A中所有球队输球场次的总和。
l(A0) : A中输球场次最多的球队所输的场次数。
c(A) : A中所包含的球队数量。

现在我们先把所有n支球队按照最终排名列出来：
(1, 2, 3, 4, ...m-2, m-1) (m, m+1, m+2, ...n-1, n)
[----------H组----------]  [---------T组---------]

人为把这些球队分为两组——H和T。c(H)=m-1，c(T)=n-m+1。显然T1是最后一支出线的球队，它所赢的场次是所有m支出线球队中最少的。现在需要求w(T1)可能的最小值。
首 先假设H和T之间的比赛H组的球队全部获胜。那么w(T)就等于T组内部所比赛的总场次数，即w(T)=(n-m)+(n-m-1)+(n-m- 2)+...+2+1=(n-m)*(n-m+1)/2。在这种情况下，w(T1)大于等于w(T)/c(T)，即(n-m)/2。当且仅当T中所有球队 获胜场次相同，并且n-m为偶数时，w(T1)取到最小值(n-m)/2。
如果H和T之间的比赛H组的球队不是全部获胜，那么T组中会有部分球队的获胜场次增加，使得w(T)增大，从而w(T1)也增大。因此要想w(T1)最小，必须满足H中的球队全部赢了T中的球队这个前提条件。

由于w(T1)>=(n-m)/2，因此可得出第一个问题的结论：当n-m为偶数时，最少赢(n-m)/2场可能出线；当n-m为奇数时，最少赢(n-m+1)/2场可能出线。

对于第二问，我们完全可以把问题变化一下，首先看看下面这个问题：
n支球队打循环赛，后n-m支球队被淘汰。每场比赛皆有胜负，没有平局。问一支球队最少输多少场仍可能被淘汰？

为什么要提出这个问题？我们想一想，一支球队不可能被淘汰，不就是一定出线么？我们知道了有可能被淘汰的输球场次最小值，也就知道了有可能被淘汰的获胜场次最大值，只要大于这个值，就一定出线。

同样的，我们把n支球队按排名列出来。不过这次倒过来排，谁输得多谁排前面：
(1, 2, 3, 4, ...n-m-2, n-m-1) (n-m, n-m+1, ...n-1, n)
[------------T组------------]  [---------H组--------]

这 次的c(T)=n-m-1，c(H)=m+1。H0是第n-m支球队，也是最后一支被淘汰的球队。根据上面第一问的解答过程和结论，可以得出l(H0)>=l(H)/c(H)=((m+1)*m/2)/m+1=m/2。由于w(H0)+l(H0)=n-1（每支球队总共进行n-1场比赛），故 w(H0)<=n-1-m/2。也就是说，一支球队最多赢n-1-m/2场仍有可能被淘汰，那么它赢的场次大于这个值就一定出线。

第二问的结论：当m为偶数时，最少赢n-m/2场一定出线；当m为奇数时，最少赢n-(m+1)/2场一定出线。