算法1-比赛出线问题


足球比赛,一个小组有8支球队进行单循环赛,胜者积3分,平则算法同积1分,负则不积分,规定积分最高的4支球队出线,则出线至少需要多少分?未出线最多可能有多少分?

循环赛的概念是每一支球队会与其他所有球队各进行一场比赛。8支球队共进行8*7/2=28场比赛。


1、出线至少需要多少分?

  • 我的解释:分数最少还要出线,所以优先输掉比赛,其次是打平。所以输掉3场,也就是输给了3个队(输给4个队,就不能保证分数最少出线了)。然后和剩下的4个队打平,这样也就是有5支队伍都只有4个积分,剩下3支都赢了剩下的5支。这样,5个4分的队伍争第四名,则出线至少要4个积分

  • 别人的解释:赢得比赛积分最快,打平积分增长慢,输掉比赛积分不变。如果想以最少的积分赢,着眼点应该在第四名上。对于第四名,如果想要满足以最少的积分赢,那么他应该输给比他强的人(与第一名、第二名、第三名比赛不积分),与所有不如自己的人打平(与第五名、第六名、第七名、第八名比赛,每场积一分),这样,第四名得分最少为4分


2、未出线最多可能有多少分?

  • 我的解释: 不出线分数还要最多,所以优先赢得比赛,其次打平。所以赢3场(赢4场就不能保证分数最多还不出线了),也就是赢了3个弱队,与剩下的4个队都打平。这样一共5个强队,每个强队都赢了3个弱队,强队之间都赢2场输2场(强队之间打平的话4分,2输2赢要6分,所以优先赢),这样也就是3x3+2x3=15分,所以有5支15分的队来争取不要不出线。这样,不出线最多能拿15分。**

  • 别人的解释: 考虑第四名与第五名并列,积分相同(通过其他方式角逐第四名)。
    这样有五个强队(前五名),三个弱队(后三名),假设后三名的球队与前五名的球队比赛时,都输给前五名,这样,前五名的每一支球队通过与后三名的球队比赛都获得3x3=9分,前五名球队的比赛,每个球队会参加4场比赛,假设,每个球队都赢两场,负两场,那么前五只球队在这个过程中每人获得2x3=6分,加上与后三名比赛积分6+9=15分,前五名并列(通过其他方式角逐名次),未出线最多获得15分


0 Comments