B1490 【入门】坐标排序
大约 2 分钟
B1490 【入门】坐标排序
【算法】 排序
【C++】 sort、结构体、pair、cmp 比较函数
【难度】 入门
一、题目简述
输入 个不同的坐标 ,按 轴的值从小到大排序。如果 相同,则按照 从小到大排序。
二、解题思路
2.1 双关键字排序
- 第一关键字:,升序
- 第二关键字:,升序
这是最简单的双关键字排序,两个关键字都是升序。
2.2 两种写法
写法一:结构体 + cmp
struct Point {
int x, y;
};
bool cmp(Point a, Point b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}写法二:用 pair<int, int>
pair 默认按 first 升序,first 相同按 second 升序——完美匹配本题要求!直接用默认的 sort 即可,无需写 cmp。
pair<int, int> a[N];
sort(a, a + n); // 默认比较规则恰好满足要求推荐写法二,代码最简洁。
2.3 手动模拟
输入:
4
2 4
1 5
2 3
3 1排序过程:
| 原顺序 | x | y |
|---|---|---|
| #1 | 2 | 4 |
| #2 | 1 | 5 |
| #3 | 2 | 3 |
| #4 | 3 | 1 |
排序后(先按 x,x 相同按 y):
| x | y |
|---|---|
| 1 | 5 |
| 2 | 3 |
| 2 | 4 |
| 3 | 1 |
三、参考代码
3.1 使用 pair(推荐)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
pair<int, int> a[1005];
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a, a + n); // pair 默认先比 first,再比 second
for (int i = 0; i < n; i++) {
cout << a[i].first << " " << a[i].second << endl;
}
return 0;
}3.2 使用结构体(更清晰)
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
};
bool cmp(Point a, Point b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
int main() {
int n;
cin >> n;
Point a[1005];
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
}
sort(a, a + n, cmp);
for (int i = 0; i < n; i++) {
cout << a[i].x << " " << a[i].y << endl;
}
return 0;
}四、复杂度分析
- 时间复杂度:,排序开销。
- 空间复杂度:,存储坐标数组。
五、知识扩展
5.1 pair 的比较规则
pair 的比较是先比较 first,first 相等再比较 second。比较方向是升序(< 运算符)。
pair<int, int> p1 = {2, 5};
pair<int, int> p2 = {2, 3};
// p1 > p2,因为 first 相同,second: 5 > 3如果本题要求 升序、 降序,则 pair 的默认规则不适用,需要手写 cmp 或使用结构体。
