题单 · 习题解析

洛谷 U269713 结构体排序-世界杯

积分 → 净胜球 → 胜负关系 → 编号,结构体多关键字排序

原题:洛谷 U269713出自 第 10 章 排序:冒泡 → 归并 → 快排 的题单题面本地存档:2026-10-18
⚠ 先自己写一遍,再往下看

这一页不是标准答案,是一条阶梯:把大多数人真实会写出的第一版摆出来, 看它错在哪、慢在哪,再一步一步改。所以它对「已经自己动手撞过一次墙」的人最有用。
还没写过的话,先去写 —— 写出来的哪怕是错的,也比直接看这一页收获大。

0题目原文(本地存了一份)

为什么要在这儿抄一份题面

原题在洛谷上(页头有链接)。别人的网站不归我们管,打不开、改版、题号调整都可能发生。 所以每个解析页都把题面转录一份存在本地,跟着仓库一起进版本库。

转录自洛谷 U269713,日期见页头。两边不一致时信原站。

题目描述

世界杯小组赛,4 支队伍打 6 场,按积分、净胜球、胜负关系、抽签(编号字典序)排名,输出前两名出线队伍。

输入格式

输入共 6 行,每行形如 A->B 1:0,表示一场比赛的对阵和比分;输入顺序不确定。

输出格式

按排名顺序输出两个出线队伍,每行一个。

输入输出样例

输入

A->B 0:0
A->C 0:0
A->D 0:0
B->C 0:0
B->D 0:0
C->D 0:0

输出

D
C
学生版:一页看懂这道题

这道题考什么:结构体排序的综合题 —— 先把 6 场比赛累加成每队的积分、进球、失球,再按多关键字排序。

最容易错的两处

  1. 净胜球写成 ga - gf(符号反了),或者积分赢球加 1 而不是 3。
  2. 绝对平局时忘了「编号字典序靠后的排前面」这条抽签规则。

能 AC 的:u269713。cmp:积分降序 → 净胜球降序 → 直接交手胜负 → 编号降序。

下面每一步里灰色的「深入」块是折叠的:那是这些结论怎么实测出来的,第一遍可以跳过。

1累加 + 排序

u269713.cpp★ 这一版就能 AC
#include <bits/stdc++.h>
using namespace std;
struct Team {
char name;
int pts = 0, gf = 0, ga = 0;
int net() const { return gf - ga; }
};
int res[4][4]; // res[a][b]: 1 if a beat b, -1 if lost, 0 draw/not played
int main() {
vector<Team> t(4);
for (int i = 0; i < 4; i++) t[i].name = 'A' + i;
string line;
// read 6 lines: "A->B 1:0"
for (int k = 0; k < 6; k++) {
if (!getline(cin, line)) break;
if (line.empty()) { k--; continue; }
char a, b; int sa, sb;
// parse
// format: X->Y s1:s2
sscanf(line.c_str(), " %c->%c %d:%d", &a, &b, &sa, &sb);
int ia = a - 'A', ib = b - 'A';
t[ia].gf += sa; t[ia].ga += sb;
t[ib].gf += sb; t[ib].ga += sa;
if (sa > sb) { t[ia].pts += 3; res[ia][ib] = 1; res[ib][ia] = -1; }
else if (sa < sb) { t[ib].pts += 3; res[ia][ib] = -1; res[ib][ia] = 1; }
else { t[ia].pts += 1; t[ib].pts += 1; res[ia][ib] = 0; res[ib][ia] = 0; }
}
sort(t.begin(), t.end(), [&](const Team &x, const Team &y) {
if (x.pts != y.pts) return x.pts > y.pts;
if (x.net() != y.net()) return x.net() > y.net();
int ix = x.name - 'A', iy = y.name - 'A';
if (res[ix][iy] != 0) return res[ix][iy] > 0;
return x.name > y.name; // absolute tie: larger letter first
});
cout << t[0].name << "\n" << t[1].name << "\n";
return 0;
}
点一下即可编辑
输入(stdin)
输出
点「运行 ▶」看结果
★ 先把比赛变成每个队的统计

读入 6 场,每队累加积分、进球、失球;净胜球 = 进球 − 失球。

cmp 四层:积分 → 净胜球 → 直接交手 → 编号(绝对平局时大者优先)。