首页 > 其他 > 详细

UVa LA 4094 WonderTeam 构造 难度: 1

时间:2019-04-12 22:05:15      阅读:189      评论:0      收藏:0      [点我收藏+]

题目

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2095


题意

球赛,n个球队,每两个之间赛两场,胜得三分,平得1分。梦之队是胜利场数最多的队伍,问梦之队的最低排名。

 

思路

明显,可以令梦队和其他队伍都相差1个胜局。

那么不妨干脆设梦队胜局为2,其他队伍胜局数为1

由于每个队伍只能参与2n-2场比赛,让情况尽可能对梦队不利,也就是其他队伍的胜局都来自于梦队,同时其他队伍之间的比赛都是平局

梦队参与的胜局,平局,输局为 2, n - 3, n - 1,总分为n + 3

一般队伍与梦队平局,胜局,平局,输局为 1, 2n - 3, 0,总分为2n

差队伍输给了梦队,胜局,平局,输局为 1, 2n - 4, 1,总分为2n - 1。

那么何时梦队的结果比一般队伍差? n + 3 < 2n,得到 n > 3

何时梦队结果比差队伍还差?n + 3 < 2n - 1,得到n > 4

也就是说

n <= 3,梦队最低也是第一名

n == 4,梦队最低是第二名,因为此时一般队伍有4 - 2 - 1 = 1个。

n >= 5, 梦队可能是最后一名。

 

感想

1. 读完题目之后不知为何心中坚定认为梦之队前面只能有第一名,也就是说梦之队前面的队伍得分是一样的,为此怎么构造也构造不出来

 

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1e3 + 3;
typedef pair<int, int> Pair;
int n;
int main() {
	int T;
	//scanf("%d", &T);
	freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
	//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
	for (int ti = 1; scanf("%d", &n) == 1 && n; ti++) {
		if (n < 4)puts("1");
		else if (n == 4) puts("2");
		else {
			printf("%d\n", n);
		}
	}
	return 0;
}

  

UVa LA 4094 WonderTeam 构造 难度: 1

原文:https://www.cnblogs.com/xuesu/p/10698862.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!