题目的主要信息：

输入任意用户、成绩序列，可以获得成绩从高到低或从低到高的排列,相同成绩都按先录入排列在前的规则处理。

方法一：

用user结构保存用户的姓名和成绩，用一个vector保存用户成绩单表，flag中储存着排序信息，flag=1表示从低到高排序，flag=0表示从高到低排序。stable_sort函数能保证稳定的排序，因此可以满足题目中同成绩都按先录入排列在前的规则处理的要求，对于flag的不同值，用compare0和compare1重载stable_sort函数。排序后，输出整个用户成绩单。 alt

具体做法：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

struct user {//用户结构
	string name;//姓名
	int score;//分数
};

bool compare0(user a, user b) {
	return a.score  > b.score ;
}

bool compare1(user a, user b) {
	return a.score < b.score;
}

int main() {
	int n,flag;
	while (cin>>n>>flag) {
		vector<user> userForm;
		for (int i = 0; i < n; i++) {//输入成绩单
			user temp;
			cin >> temp.name >> temp.score ;
			userForm.push_back(temp);
		}
		if(flag){//从低到高排序
			stable_sort(userForm.begin(), userForm.end(), compare1);//重载稳定排序
        }else{//从高到低排序
            stable_sort(userForm.begin(), userForm.end(), compare0);//重载稳定排序
        }
		for (int i = 0; i < n; i++) {//输出成绩单
			cout << userForm[i].name << " " << userForm[i].score << endl;
		}
	}
    return 0;
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，stable_sort排序是快速排序，时间复杂度为 $O (n l o g_{2} n)$ 。
空间复杂度： $O (n)$ ，userForm的大小为n。

方法二：

逐个输入建立成绩和姓名之间的映射，能保证相同成绩的用户在同一映射下，且按照输入顺序排序。用flag中储存排序信息，flag=1表示从低到高排序，flag=0表示从高到低排序。begin和end操作产生指向容器内第一个元素和最后一个元素的下一个位置的迭代器，能够按照从小到大的顺序输出映射。rbegin和rend产生指向容器内最后一个元素和第一个元素的下一个位置的迭代器，能够按照从大到小顺序输出映射。在相同成绩的映射下，按照输入顺序输出用户名。

具体做法：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    int flag;
    while (cin >> n >> flag) {
        map<int, vector<string>> mp;
        string name;
        int score;
        for(int i = 0; i < n; i++){//建立成绩和名字的映射
            cin >> name;
            cin >> score;
            mp[score].push_back(name);
        }
        if (flag == 0) {//从高到低
        for (auto it = mp.rbegin(); it != mp.rend(); ++it) {//逆序遍历
            for (int i = 0; i < it->second.size(); i++) {//成绩相同时，按照输入顺序输出
                cout << it->second[i] << " " << it->first << endl;
            }
        }
        } else {//从低到高
            for (auto it = mp.begin(); it != mp.end(); ++it) {//顺序遍历
                for (int i = 0; i < it->second.size(); i++) {//成绩相同时，按照输入顺序输出
                    cout << it->second[i] << " " << it->first << endl;
                }
            }
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下遍历一遍所有用户成绩和名字的映射。
空间复杂度： $O (n)$ ，最坏情况n个用户的成绩都不相同，mp的大小为n。

题解 | #成绩排序#

题目的主要信息：

方法一：

方法二：