小朋友的游戏(训练排序算法)-蒲公英云

小朋友的游戏(训练排序算法)

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; 
}