[数据结构与算法]Acwing考研算法辅导课——成绩排序

预备知识

stable_sort()使用情况

当指定范围内包含多个相等的元素时，sort() 排序函数无法保证不改变它们的相对位置。那么，如果既要完成排序又要保证相等元素的相对位置，可以使用 stable_sort() 函数。

stable_sort()用法

  bool mycomp(int i, int j) {
    return (i < j);}
              
   //从小到大排
   std::stable_sort(myvector.begin(), myvector.begin() + 4); //(12 32 45 71) 26 80 53 33
    //调用第二种语法格式，利用STL标准库提供的其它比较规则（比如 greater<T>）进行排序
    //从大到小排
    std::stable_sort(myvector.begin(), myvector.begin() + 4, std::greater<int>()); //(71 45 32 12) 26 80 53 33
    //自定义排序
    //调用第二种语法格式，通过自定义比较规则进行排序,这里也可以换成 mycomp2()
    std::stable_sort(myvector.begin(), myvector.end(), mycomp);//12 26 32 33 45 53 71 80

bool operator < (const p &a)const 运算符的重载

可参考 C/C++对bool operator < (const p &a)const的认识，运算符重载详解(杂谈).

<返回类型说明符> operator <运算符符号>(<参数表>) {      <函数体> }

题目1

定学生的成绩单，成绩单中包含每个学生的姓名和分数，请按照要求将成绩单按成绩从高到低或从低到高的顺序进行重新排列。

对于成绩相同的学生，无论以哪种顺序排列，都要按照原始成绩单中靠前的学生排列在前的规则处理（使用stable_sort()）。

输入格式

第一行包含整数 N，表示学生个数。

第二行包含一个整数 0 或 1，表示排序规则，0 表示从高到低，1 表示从低到高。

接下来 N 行，每行描述一个学生的信息，包含一个长度不超过 10 的小写字母构成的字符串表示姓名以及一个范围在 0～100 的整数表示分数

输出格式

输出重新排序后的成绩单。

每行输出一个学生的姓名和成绩，用单个空格隔开。

输入样例

4
0
jack 70
peter 96
Tom 70
smith 67

输出样例

peter 96
jack 70
Tom 70
smith 67

代码

#include <bits/stdc++.h>
#include <vector>
const int N = 1010;
using namespace std;

struct Person
{
    string name;
    int score;

    bool operator<(const Person &t) const
    {
        return score < t.score;
    }
    bool operator>(const Person &t) const
    {
        return score > t.score;
    }

} p[N];

int main()
{

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        cin >> p[i].name >> p[i].score;

    if (m == 0)
    {
        stable_sort(p, p + n, greater<Person>());
    }
    else
    {
        stable_sort(p, p + n);
    }

    for (int i = 0; i < n; i++)
        cout << p[i].name << " " << p[i].score << endl;

    return 0;
}

题目2

给定学生的成绩单，成绩单中包含每个学生的学号和分数，请将成绩单按成绩从低到高的顺序重新排序。

如果学生的成绩相同，则按照学号从小到大的顺序进行排序

输入格式

第一行包含整数 N，表示学生数量。

接下来 N 行，每行包含两个整数 p 和 q，表示一个学生的学号和成绩。

学生的学号各不相同。

输出格式

输出重新排序后的成绩单。

每行输出一个学生的学号和成绩，用单个空格隔开。

输入样例

3
1 90
2 87
3 92

输出样例

2 87
1 90
3 92

代码

#include <bits/stdc++.h>
#include <vector>
const int N = 110;
using namespace std;

struct student
{
    int id;
    int score;

    bool operator<(const student &t) const
    {
        if (score != t.score)
            return score < t.score;
        else
            return id < t.id;
    }

} q[N];

int main()
{

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> q[i].id >> q[i].score;

    sort(q, q + n);
    for (int i = 0; i < n; i++)
        cout << q[i].id << " " << q[i].score << endl;

    return 0;
}

完结

今天也要加油呀