小朋友的游戏(训练排序算法)
n 个小朋友在玩游戏，编号依次为 1∼n。
每个小朋友都有一个身份，为 rat（老鼠）、woman（女人）、child（孩子）、man（男人）、captain（舰长） 之一。
已知，这几种身份的优先级是有区别的：
rat 为第一优先级。
woman 和 child 为第二优先级。
man 为第三优先级。
captain 为第四优先级。
现在，要给小朋友们排队，排队的规则为：
对于不同优先级的小朋友，优先级越靠前（越小）则在队伍中的位置越靠前。
对于同一优先级的小朋友，编号越小则在队伍中的位置越靠前。
请你确定小朋友们的具体排队顺序。
输入格式:
第一行包含整数 n
。
接下来 n 行，其中第 i 行用来描述编号为 i 的小朋友，首先包含一个字符串，表示小朋友的名字，然后包含一个字符串，表示他的身份。
每个小朋友的名字都是一个长度范围在 [1,10] 的由英文字母构成的字符串，其中首字母大写，其余小写。
小朋友的名字两两不同。
表示身份的字符串一定是 rat、woman、child、man、captain 之一。
保证身份为 captain 的小朋友有且仅有一个。
输出格式:
共 n 行，其中第 i 行输出排在队伍中第 i 位的小朋友的名字。
输入样例:
6
Jack captain
Alice woman
Charlie man
Teddy rat
Bob child
Julia woman
输出样例:
Teddy
Alice
Bob
Julia
Charlie
Jack
数据范围
前 3 个测试点满足 1 ≤ n ≤ 10。
所有测试点满足 1 ≤ n ≤ 100。
算法解析
分析这个题，乍一看感觉还是蛮难的，不知道怎么进行排序，要求怎么这么多，然后在细想，好像可以做，就是用c++自带的类排序呀，定义一个类，然后这个类包含题目中要求的成员，然后在制定一个排序规则就好了，想好了之后就简单，这里我还做了一个小小的优化，就是使用map容器，对优先级进行了优化，把文字转换为了数字，这样更加方便于操作。
提交代码
#include<bits/stdc++.h> using namespace std; const int N = 1010; map<string, int> mp; class T{ public: int num; string name; string name2; T(int num, string name, string name2) { this->num = num; this->name = name; this->name2 = name2; } }; bool compare(T a, T b) { if (mp[a.name2] == mp[b.name2]) { return a.num < b.num; } else { return mp[a.name2] < mp[b.name2]; } // return true; return mp[a.name2] < mp[b.name2]; } int main() { int n; cin >> n; vector<T> v; mp.insert(make_pair("rat", 1)); mp.insert(make_pair("woman", 2)); mp.insert(make_pair("child", 2)); mp.insert(make_pair("man", 4)); mp.insert(make_pair("captain", 5)); for (int i = 0; i < n; ++ i) { string name, name2; cin >> name >> name2; T t(i, name, name2); v.push_back(t); } sort(v.begin(), v.end(), compare); for (int i = 0; i < n; ++ i) { cout << v[i].name << '\n'; } return 0; }
