首页 > 代码库 > UVA1418-WonderTeam(推理+贪心)

UVA1418-WonderTeam(推理+贪心)

题目链接


题意:有n支队伍比赛,每两支队伍打两场(主客场各一次),胜得3分,输不得分,平得1分。比赛结束之后会评选出一个梦之队,它满足如下条件:进球总数最多(不能并列),胜利场数最多(不能并列),丢球总数最少(不能并列)。求梦之队的最低可能排名。一支得分为p的球队的排名等于等分严格大于p的球队的个数加1.

思路:其实3个限定条件只有胜利场数最多有用,因为梦之队可以在胜利场次大比分获胜,输的比赛都是1:0负于对手,其他两个就无关紧要了。要让梦之队排名尽量低,也就意味着让其得分尽量低。那么我们假设梦之队的胜利场数为2,其他球队的胜利场数都为1,那么满足了上述条件,也让梦之队的得分尽量低。 
当参赛球队为n支时的战绩及分数: 
梦之队:胜2场,负n-1,平n-3 = 2*3+n-3 = 3+n 
其中2支球队:胜1场,负1场,平2*n-4 = 1*3+2*n-4 = 2*n-1 
剩余队伍(当n>3时存在剩余队伍):胜1场,负0场,平2*n-3 = 2*n 
所以根据分数可以得出排名。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
    int n; 
    while (scanf("%d", &n) && n) {
        if (n <= 3)
            printf("1\n");
        else if (n == 4)
            printf("2\n");
        else
            printf("%d\n", n);
    }
    return 0;
}