洛谷P17815 [ICPC 2019 Nanchang R] Who is the Champion 题解
洛谷P17815 [ICPC 2019 Nanchang R] Who is the Champion 题解
题目链接：P17815 [ICPC 2019 Nanchang R] Who is the Champion
题意：
足球可能是这个国家最受欢迎的体育运动。然而，国家队在世界舞台上的战绩并不理想。为了激励年轻球员，每年都会举办全国足球锦标赛。
今年，共有 \(n\) 支球队参加锦标赛。按照惯例，采用单循环赛制，每支球队与其他每支球队各比赛一场。一场标准的比赛双方各需要十名场上球员和一名守门员，总共有 \(22\) 名球员参与。他们在长方形的草地球场上相互对抗，防守自家球门，攻击对方球门。
在 \(90\) 分钟的比赛中，双方不断尝试射门。比赛结束时，进球数较多的一方获胜，并在积分榜上获得 \(3\) 分，而失利方则不得分。一种非常特殊但常见的情况是双方进球数相同，即平局；此时双方各在积分榜上获得 \(1\) 分。
赛季结束后，联赛将宣布总积分最高的球队为冠军。如果两支或更多球队的总积分相同，则总净胜球（用所有联赛比赛中的总进球数减去总失球数计算）最高的球队将成为冠军。最坏的情况是若干支球队的总积分和净胜球都相同，这将通过额外的附加赛来解决。
输入格式：
第一行包含一个整数 \(n\) \((1\le n \le 100)\) 表示参赛球队的数量。
接下来的 \(n\) 行，每行包含 \(n\) 个整数。第 \(i\) 行中的第 \(j\) 个整数为非负整数且不超过 \(5\)，表示第 \(i\) 支球队对阵第 \(j\) 支球队时的进球数。
我们保证对于所有 \(1\le i \le n\)，有 \(a_{i,i}=0\)。
输出格式：
如果联赛能够决出冠军，输出将获得冠军的球队的编号；如果需要组织附加赛，则输出
play-offs（不带引号）。
好久没有写题目了，写一道普及组送分题练练手，我就当各位读者是萌新了，写得详细一点。
我们只需要设计程序，统计出积分最高的队伍、比较与第二名的净胜球的差异，输出队伍 ID 即可。
我们可以建一个 struct 来记录 ID、积分和净胜球，就叫 node 好了，叫什么都一样。
尝试设计一个排序方式。记 \(x,y\) 为需要比较的两个 node ，设计以下排序规则：
- 如果 \(x,y\) 的积分不相同，那么 \(x < y\) 即 \(x\) 排在 \(y\) 前面的条件是 \(x\) 的积分小于 \(y\) 的积分
- 如果 \(x,y\) 的积分相同，那么 \(x<y\) 即 \(x\) 排在 \(y\) 前面的条件是 \(x\) 的净胜球小于 \(y\) 的净胜球
这样排序之后，最后一个 node 元素就是积分最大的，或者积分最大的里净胜球最高的那个，判断即可
时间复杂度 \(O(n^2)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(105))
int n, a[N][N], b[N], c[N];
struct node { int id, u, v; } d[N];
bool operator<(node x, node y) { return x.u != y.u ? x.u < y.u : x.v < y.v; }
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
rep(i, 1, n) rep(j, 1, n) cin >> a[i][j];
rep(i, 1, n) rep(j, 1, n) if(i != j)
{
if(a[i][j] > a[j][i]) { b[i] += 3; }
else if(a[i][j] == a[j][i]) { b[i] += 1; }
c[i] += a[i][j]; c[j] -= a[i][j];
}
rep(i, 1, n) d[i] = {i, b[i], c[i]};
sort(d + 1, d + 1 + n);
if(n > 1 && d[n].u == d[n - 1].u)
{
if(d[n].v > d[n - 1].v) cout << d[n].id << '\n';
else { cout << "play-offs\n"; }
}else { cout << d[n].id << '\n'; }
return 0;
}题外话：
康复训练想着先写个送分题练练手居然调了整整一个小时，一个小时！！孩子们 What can I say?
找了半天错最后发现我写了这样一段代码，而且我看了半天居然一点都没看出来问题？？？
bool operator<(node x, node y) { return x.u == y.u ? x.u < y.u : x.v < y.v; }孩子们，这已经不是一般的粗心大意了，这是一个严重的认知错误甚至障碍啊！！！
最近休息的很不好，精神状态一直不在线，不过我没想到居然会有这么严重
这意味着我自认为在思考，其实压根就没在思考，虽然我以前就发现过这样的问题，但是这次……
这次我清晰的记录了我的思维过程，我发现我根本就没有调用到数学思维的那块部分……
就算是现在我试图调用，也根本调用不了，你们懂吗，你们懂那种无法思考的感觉吗？？这真是太奇怪了。
好吧孩子们我就不在这里写太多这种东西了，我得去好好休息了，更多这种乱七八糟内容我就在分站更新了
![洛谷P17815 [ICPC 2019 Nanchang R] Who is the Champion 题解](/qwq/img/p182.webp)
