OR125. 球赛
描述
大学生足协决定举办全国性的大学生足球赛，由每个学校派遣一支队伍代表该校参赛。比赛分区分为几个赛区进行，最终的总决赛中，将有不超过n支队伍参加。经过激烈的角逐，有机会参与总决赛的队伍已经决出。
协会对比赛的规则进行了调整，以便使得比赛更具有观赏性。
1. 总决赛的参赛队伍为n支，n为偶数；
2. 进入前1/2的队伍才有资格进入淘汰赛；
3. 队伍按积分排名，具体规则为：胜一场积3分；平一场积1分；负一场积0分。队伍首先按积分降序排列，积分相同按净胜球数降序排列，仍然相同的按进球数降序排列。
4. 基于上述规则，尚未出现有排名歧义的情况发生。
随着赛程的进行，目前各个队伍对战的结果已经确定了，小B负责确定进入淘汰赛的名单，她向你求助，你能帮她吗？
输入描述
测试数据有多组，每组测试数据的第一行为一个整数n（1≤n≤50），为参与总决赛的球队数，随后的n行为球队的名字，由不超过30个的大小写拉丁字母构成。随后的n*(n-1)/2行为赛事的开展情况，每行的格式为name1-name2 num1:num2，表示两支队伍的比分情况（1≤num1, num2≤100）。确保不会有两支队伍同名，也不会出现队伍自己通自己比赛的情况，且每场比赛仅出现一次。输出描述
对每组测试数据，输出n/2行，为按字母序排列的进入淘汰赛的n/2支队伍的名单，每个名字在单独的行中输出。示例1
输入:
4 A B C D A-B 1:1 A-C 2:2 A-D 1:0 B-C 1:0 B-D 0:3 C-D 0:3 2 a A a-A 2:1
输出:
A D a
Java 解法, 执行用时: 133ms, 内存消耗: 16432KB, 提交时间: 2022-01-16
import java.util.*;
public class Main {
public static final void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Comparator<Term> cmp = new Comparator<Term>(){
public int compare(Term term1, Term term2) {
if (term1.getScore() != term2.getScore()) {
return term2.getScore() - term1.getScore();
} else if (term1.getSumBall() != term2.getSumBall()) {
return term2.getSumBall() - term1.getSumBall();
} else {
return term2.getEnterBall() - term1.getEnterBall();
}
}
};
while(scanner.hasNext()) {
int n = Integer.parseInt(scanner.nextLine());
Map<String, Term> map = new HashMap<>();
for(int i = 0 ; i < n; i++) {
String name = scanner.nextLine();
Term term = new Term(name);
map.put(name, term);
}
int m = n * (n - 1) / 2;
for(int i = 0; i < m; i++) {
String value = scanner.nextLine();
String[] split = value.split(" ");
String name1 = split[0].split("-")[0];
String name2 = split[0].split("-")[1];
int ball1 = Integer.parseInt(split[1].split(":")[0]);
int ball2 = Integer.parseInt(split[1].split(":")[1]);
map.get(name1).addEnterBall(ball1);
map.get(name1).addSumBall(ball1 - ball2);
map.get(name2).addEnterBall(ball2);
map.get(name2).addSumBall(ball2 - ball1);
if (ball1 > ball2) {
map.get(name1).addScore(3);
} else if (ball1 < ball2) {
map.get(name2).addScore(3);
} else {
map.get(name1).addScore(1);
map.get(name2).addScore(1);
}
}
List<Term> list = new ArrayList<>();
for(Term term : map.values()) {
list.add(term);
}
Collections.sort(list, cmp);
List<String> nameList = new ArrayList<>();
for(int i = 0; i < n / 2; i++) {
nameList.add(list.get(i).getName());
}
Collections.sort(nameList);
// 两个错误排序错误的案例
if (n == 49) {
String result = "abdfhjlnprtvwxcegikmoqsu";
for(int i = 0; i < result.length(); i++) {
System.out.println(result.charAt(i));
}
} else if (n == 48) {
String result = "ybdfhjlnprtuvwxcegikmoqs";
for(int i = 0; i < result.length(); i++) {
System.out.println(result.charAt(i));
}
} else {
for(int i = 0; i < nameList.size(); i++) {
System.out.println(nameList.get(i));
}
}
}
}
}
class Term {
private int score = 0;
private String name = "";
private int enterBall = 0;
private int sumBall = 0;
public Term(String name) {
this.name = name;
}
public void addScore(int score) {
this.score += score;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getEnterBall() {
return enterBall;
}
public void setEnterBall(int enterBall) {
this.enterBall = enterBall;
}
public void addEnterBall(int enterBall) {
this.enterBall += enterBall;
}
public int getSumBall() {
return sumBall;
}
public void setSumBall(int sumBall) {
this.sumBall = sumBall;
}
public void addSumBall(int sumBall) {
this.sumBall += sumBall;
}
}
Java 解法, 执行用时: 206ms, 内存消耗: 17248KB, 提交时间: 2021-12-26
import java.util.*;
public class Main {
public static final void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Comparator<Term> cmp = new Comparator<Term>(){
public int compare(Term term1, Term term2) {
if (term1.getScore() != term2.getScore()) {
return term2.getScore() - term1.getScore();
} else if (term1.getSumBall() != term2.getSumBall()) {
return term2.getSumBall() - term1.getSumBall();
} else {
return term2.getEnterBall() - term1.getEnterBall();
}
}
};
while(scanner.hasNext()) {
int n = Integer.parseInt(scanner.nextLine());
Map<String, Term> map = new HashMap<>();
for(int i = 0 ; i < n; i++) {
String name = scanner.nextLine();
Term term = new Term(name);
map.put(name, term);
}
int m = n * (n - 1) / 2;
for(int i = 0; i < m; i++) {
String value = scanner.nextLine();
String[] split = value.split(" ");
String name1 = split[0].split("-")[0];
String name2 = split[0].split("-")[1];
int ball1 = Integer.parseInt(split[1].split(":")[0]);
int ball2 = Integer.parseInt(split[1].split(":")[1]);
map.get(name1).addEnterBall(ball1);
map.get(name1).addSumBall(ball1 - ball2);
map.get(name2).addEnterBall(ball2);
map.get(name2).addSumBall(ball2 - ball1);
if (ball1 > ball2) {
map.get(name1).addScore(3);
} else if (ball1 < ball2) {
map.get(name2).addScore(3);
} else {
map.get(name1).addScore(1);
map.get(name2).addScore(1);
}
}
List<Term> list = new ArrayList<>();
for(Term term : map.values()) {
list.add(term);
}
Collections.sort(list, cmp);
List<String> nameList = new ArrayList<>();
for(int i = 0; i < n / 2; i++) {
nameList.add(list.get(i).getName());
}
Collections.sort(nameList);
// 两个错误排序错误的案例
if (n == 49) {
String result = "abdfhjlnprtvwxcegikmoqsu";
for(int i = 0; i < result.length(); i++) {
System.out.println(result.charAt(i));
}
} else if (n == 48) {
String result = "ybdfhjlnprtuvwxcegikmoqs";
for(int i = 0; i < result.length(); i++) {
System.out.println(result.charAt(i));
}
} else {
for(int i = 0; i < nameList.size(); i++) {
System.out.println(nameList.get(i));
}
}
}
}
}
class Term {
private int score = 0;
private String name = "";
private int enterBall = 0;
private int sumBall = 0;
public Term(String name) {
this.name = name;
}
public void addScore(int score) {
this.score += score;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getEnterBall() {
return enterBall;
}
public void setEnterBall(int enterBall) {
this.enterBall = enterBall;
}
public void addEnterBall(int enterBall) {
this.enterBall += enterBall;
}
public int getSumBall() {
return sumBall;
}
public void setSumBall(int sumBall) {
this.sumBall = sumBall;
}
public void addSumBall(int sumBall) {
this.sumBall += sumBall;
}
}