ARTICLE · 1357130
GESP 2025年6月 真题 排序 完整题解(排序)
体育课上有 n 名同学排成一队，从前往后数第 i 位同学的身高为 hᵢ，体重为 wᵢ。目前排成的队伍看起来参差不齐，老师希望同学们能按照身高从高到低的顺序排队，如果身高相同则按照体重从重到轻排序。在调整队伍时，每次只能交换相邻两位同学的位置。老师想知道，最少需要多少次交换操作，才能将队伍调整成目标顺序。
1 60
3 70
2 80
4 55
4 50
4 0
4 0
2 0
3 0
1 0
换个角度看这题：如果你是出题人，你会怎么设卡？顺着这个角度，解法反而更好记。
这道题出自 GESP 2025年6月，四级的排序题。它不难，但每年都有人在这里丢分，丢的地方还都一样。我们花十分钟把它从头捋一遍。
题目：排序
场次：2025年6月 四级｜难度：四级
知识点：基础排序
链接：https://www.acgo.cn/problemset/info/62070
体育课上有 n 名同学排成一队，从前往后数第 i 位同学的身高为 hᵢ，体重为 wᵢ。目前排成的队伍看起来参差不齐，老师希望同学们能按照身高从高到低的顺序排队，如果身高相同则按照体重从重到轻排序。在调整队伍时，每次只能交换相邻两位同学的位置。老师想知道，最少需要多少次交换操作，才能将队伍调整成目标顺序。
一句话概括：用基础排序把题目要求原样翻译成代码，属于考场上必须拿满分的题。
| 卡点 | 出题人卡的是什么 | 你要做的事 |
|---|---|---|
| 数据类型 | 用 int 装不下的人 | 累加变量用 long long |
| 边界 | 只按样例想问题的人 | 题目说「到」或者「包括」 |
| 输出格式 | 不看输出要求直接 cout 的人 | 换行、空格、顺序逐项对 |
三个卡点都不难，难的是同时想到。
出题人不会白给数据范围。范围里就藏着「能不能暴力」这个提示，顺着它往回推，解法基本就定了。
题目答案:
建议先自己写二十分钟，卡住了再看。对着抄一遍的效果，比不上自己错一遍。
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
int n, ans = 0;
scanf("%d", &n);
vector<pair<int,int>> a(n);
for (int i = 0; i < n; i ++) // 遍历
scanf("%d%d", &a[i].first, &a[i].second);
for (int i = 0; i < n; i ++) // 遍历
for (int j = i + 1; j < n; j ++) // 遍历
if (a[i] < a[j]) // 判断
ans ++;
cout << ans << '\n'; // 输出
return 0;
}
逐段过一遍会太啰嗦，我只讲决定对错的那两段。
第一段，把数据读进来。
vector<pair<int,int>> a(n);
读入这段只要盯一件事：变量类型装不装得下。其他都可以照抄。
第二段，核心处理。
scanf("%d%d", &a[i].first, &a[i].second);
for (int i = 0; i < n; i ++)
for (int j = i + 1; j < n; j ++)
if (a[i] < a[j])
ans ++;
cout << ans << '\n';
这段是整道题唯一需要想的地方，也是排序的落点。看循环时只问三句：从哪开始、到哪结束、每次加几。三句都对，这段就没错。
下面按四步验一遍，这个顺序建议你考试时也照做。
样例输入
1 60
3 70
2 80
4 55
4 50
样例输出
| 步骤 | 做什么 | 通过标准 |
|---|---|---|
| 1 | 跑题目给的样例 | 输出和样例逐字符一致，包括空格和换行 |
| 2 | 试最小的输入 | 只给一个数、只给一行，程序不崩也不越界 |
| 3 | 检查输出末尾 | 没有多余空格，最后一行有换行 |
| 4 | 跑完剩下 1 组样例 | 全部对上再提交，别只看第一组 |
题目还有 1 组样例，全部跑通再提交。
| 容易错的地方 | 错误写法 | 正确写法 |
|---|---|---|
| 累加结果溢出 | int sum = 0; | 累加变量用 long long |
| 漏掉区间右端点 | i < R | i <= R |
| 输出格式不符 | cout << ans; | cout << ans << "\n"; |
| 多组数据没清空 | 全局数组直接用 | 每组数据前 memset 或重新赋值 |
最后收个尾，三句话说完这题。
- 筛的是什么：基础排序的完整度——范围、边界、格式缺一不可。
- 要记住的：升序还是降序、按哪个字段排，写反了答案就反了。
- 下一步：找同场次另一道题，用同样的三个卡点自查一遍。
下一篇继续同场次的真题。有更短的写法，欢迎评论区贴出来。
- 本文属于《GESP 真题题解》系列，第 1 篇，真题按年份持续补齐，每篇都带完整可编译代码，题号可在 ACGO 直接提交验证。
- 还没动笔的话，先自己写一遍再回来看踩坑总结，比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注，更新会第一时间推送。
- 本系列合集目录（按年份/组别排序）
GESP 的坑多半在边界和读题上。这道排序题把该注意的点都列在上面的表里了，提交前逐条过一遍。
今天想问你：这道题的思路你能用自己的话讲给同学听吗？试试在评论区用三句话讲完。
有用就收藏一份，考前翻出来快速过一遍错题点；关注本号，真题系列每天不间断。
想要这题的可运行代码文件？后台回复 “资料” 直接拿。
本篇编号 GESP-033（公众号 MP-033）。完整目录与更多题解见博客专栏（公众号菜单「历史文章」）。
