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

ゞ浴缸里的玫瑰 2024-03-27 09:05 60阅读 0赞

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

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