首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。