描述
题目描述
首先我们是有 T组数据 ，接下来我们每组数据输入一个 n 代表的是我们有 n位同学的成绩需要我们来进行一个排序，接下来输入一个 op 这个代表的就是我们按照什么规则来排序
- 当 op == 0 时，代表我们排序要按照 从高到低来排序
- 当 op == 1 时，代表我们排序要按照 从低到高来排序 接下来就是 n 组数据，每组数据的 第一个是姓名， 第二个是成绩
样例解释
3
1
fang 90
yang 50
ning 70
3
0
moolgouua 43
aebjag 87
b 67
首先第一个 3 代表的是代表的是有三组数据，接下来的 1 是让我们把接下来的三个成绩按照从低到高的顺序来进行一个排序，那么我们经过从低到高的排序后，我们可以得到第一个样例输出
yang 50
ning 70
fang 90
然后我们对第二个样例进行一个解释， 3 代表的是有三组数据，接下来 0 代表的是我们把接下来的三组数据按照成绩从高到低排序，排序后我们可以得到这么一个结果
aebjag 87
b 67
moolgouua 43
这道题我们可以看出，我们要做的就是首先把姓名跟成绩对应存储下来，然后进行一个排序，最后我们把我们的思路进行一个化简，发现这个题是一个考察结构体排序的题目
知识点： 结构体排序
难度： 两星
题解：
解题思路：
这道题我们发现了是考察我们的一个结构体排序的知识点，但是这里面有一个需要我们注意的问题： 如果有两位同学的成绩是相同的，那么我们最后输出的顺序要按照他们输入的顺序来输出
对于这道题目来讲，我们存储我们的成绩对应姓名，使用结构体的时候空间复杂度是 O(n) 的，时间复杂度也是 O(n) 的，但是对于我们的排序来讲使用不同的排序的时候，他的时间复杂度是不一样的，假设我们使用最为暴力的双重 for 循环的排序做法，那么我们总体的时间复杂度就是 的，因为一个程序的时间复杂度是取决于他的最高的时间复杂度的
解法一 ：暴力解法
我们采用双重 for 循环的方式，然后排序成绩以及他的id，我们的代码实现如下
时空复杂度分析
首先我们开辟了结构体数组用以存储我们的姓名，成绩，以及输入的顺序，这里我们输入的时间复杂度是 O(n) 的，然后空间复杂度是 3*n 的，但是在算法竞赛中，我们前面的常数是忽略的，所以我们这个的空间复杂的是 O(n) 的，然后我们的暴力排序算法经过了 n * (n - 1) / 2 次运算的，然后计算时间复杂度就是的时间复杂度，最后这种暴力求解的方法，空间复杂度是O(n) 的，时间复杂度是 的
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
struct node {
string name;
int val, id;
} a[N];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
while(cin >> n) { // 多组输入我们的n组数据
int op;
cin >> op; // 输入我们的排序规则
for (int i = 1; i <= n; i++) {
cin >> a[i].name >> a[i].val;
a[i].id = i;
}
// 输入我们的 n 组的名字以及成绩，最后把id赋值上去
if (op == 1) {
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i].val > a[j].val) swap(a[i], a[j]); // 首先我们判断如果我们的成绩前面的比后面的大，那么我们交换
else if (a[i].val == a[j].val) {
if (a[i].id > a[j].id) swap(a[i], a[j]);
// 如果我们的成绩相同，前者的id比后者的id大，我们也要交换
}
}
}
} else {
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i].val < a[j].val) swap(a[i], a[j]); // 首先我们判断如果我们的成绩前面的比后面的小，那么我们交换
else if (a[i].val == a[j].val) {
if (a[i].id > a[j].id) swap(a[i], a[j]);
// 如果我们的成绩相同，前者的id比后者的id大，我们也要交换
}
}
}
// 这里是如果两者的成绩相同，那么返回id较小的，否则返回成绩大的
}
// 我们对两次进行一个排序
for (int i = 1; i <= n; i++) {
cout << a[i].name << " " << a[i].val << endl;
}
// 输出我们排序后的结果
}
return 0;
}
图解算法
解法二 ： 快速排序 - 自定义排序函数
时空复杂度分析
这里我们要追求更快的处理速度，那么我们要采取更快的一个排序的方式，这里我们选择了快速排序，这次我们采用的算法的空间复杂度是O(n) 的，但是我们的时间复杂度使用的是快速排序，快速排序的时间复杂度是O(nlogn) 的，那么我们这种快速排序搭配结构体的算法的总体的时间复杂度就是 O(nlogn) 的，空间复杂度就是O(n) 的，可能会有小伙伴疑问，为什么输入的时间复杂度O(n) 我们在这里面不考虑呢？ 因为在我们的算法竞赛中，一个算法的时间复杂度取决于的是它最慢的一个时间，换种理解方式就是，在n很大的时候，我们的小的地方是可以忽略不记的，所以我们时间复杂度取得是一个程序中的瓶颈的时间复杂度
这里我给出两种写法，第一种是自己定义比较函数一般成为 cmp
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
struct node {
string name;
int val, id;
} a[N];
bool cmp1(node wa, node wb) {
if (wa.val == wb.val) return wa.id < wb.id;
return wa.val < wb.val;
}
// cmp1这里是如果两者的成绩相同，那么返回id较小的，否则返回成绩小的
bool cmp2(node wa, node wb) {
if (wa.val == wb.val) return wa.id < wb.id;
return wa.val > wb.val;
}
// cmp2这里是如果两者的成绩相同，那么返回id较小的，否则返回成绩大的
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
while(cin >> n) { // 输入有多少组待排序的数据
int op;
cin >> op; // 输入排序规则
for (int i = 1; i <= n; i++) {
cin >> a[i].name >> a[i].val;
a[i].id = i;
}
// 将我们的姓名和成绩输入，并且记录下来id，就是输入的顺序
if (op == 1) {
sort(a + 1, a + n + 1, cmp1);
// 以cmp1的规则排序
} else {
sort(a + 1, a + n + 1, cmp2);
// 以cmp2的规则排序
}
for (int i = 1; i <= n; i++) {
cout << a[i].name << " " << a[i].val << endl;
}
}
return 0;
}
快速排序 - 匿名函数 (c++11及以后)
第二种就是用到了c++11出现的匿名函数的这个语法
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
struct node {
string name;
int val, id;
} a[N];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
while(cin >> n) {
int op;
cin >> op;
for (int i = 1; i <= n; i++) {
cin >> a[i].name >> a[i].val;
a[i].id = i;
}
if (op == 1) {
sort(a + 1, a + n + 1, [](node wa, node wb) -> bool {
if (wa.val == wb.val) return wa.id < wb.id;
return wa.val < wb.val;
});
// 这里是如果两者的成绩相同，那么返回id较小的，否则返回成绩小的
} else {
sort(a + 1, a + n + 1, [](node wa, node wb) -> bool {
if (wa.val == wb.val) return wa.id < wb.id;
return wa.val > wb.val;
});
// 这里是如果两者的成绩相同，那么返回id较小的，否则返回成绩大的
}
for (int i = 1; i <= n; i++) {
cout << a[i].name << " " << a[i].val << endl;
}
}
return 0;
}
京公网安备 11010502036488号