我假设输了 0 分,平局 1 分,赢了 2 分。
For each team t
Sort the teams by their current point table so the last place
team(s) come first and the top teams come last. Put all teams tied with t before t.
Let i be the position of team t in this list
From here on I'll name teams by their position in the list. So we have
from left to right, teams currently worse than i, teams tied with team i, team i,
and finally teams better than i.
Make a working copy of your matrix. For the rest of this
iteration I'll implicitly refer to the working copy.
Suppose (in the working copy) that team i has loses all its remaining games.
For j from 0 up to i
Make a backup copy of the working copy.
for( k:=n-1 ; k < j and j is behind or tied with i ; k := k-1 )
If k hasn't played j and j is behind i
suppose that j beats k
Else if k hasn't played j /* and is tied with k */
suppose that j ties k
if j is still behind i
revert to the backup made before the preceding loop
discard the backup copy
for all games j has yet to play suppose j loses
At this point, all remaining games in the working copy are between teams ahead
of team i, assume all remaining games are ties.
Now (if we have really constructed a worst case scenario) the rank of team i
in the working copy is the worst it can do. I.e. team i beats "count
我不完全确定这给出了确切的下限。上限是对称的。