算法-查找排序-之成绩排序

算法-查找排序-之成绩排序

 

 

 算法-查找排序-之成绩排序

算法-查找排序-之成绩排序

 

 

 

 分析和思路:

把成绩保存到map或者vector中,然后进行排序。这道题关键是处理那个成绩相等时,排序后依然保持相对顺序不变的问题,费了好大的心思,发现效果依然不是自己想要的,写出的代码如下:

 1 #include "iostream"
 2 #include <vector>
 3 #include <map>
 4 #include "algorithm"
 5 #include <unordered_map>
 6 using namespace std;
 7 int main()
 8 {
 9     
10     int number=0;
11     int mode=0;
12     //cin>>number;
13     //cin>>mode;
14     string name;int score;
15    
16    
17     while(cin>>number>>mode)
18     {
19          vector<int> vector_score;
20         //std::unordered_map<std::string,int> mymap={"key",111};
21          unordered_map<string,int> m;
22          int i=0;//注意细节
23         while(i<number)
24         {
25             cin>>name;
26             cin>>score;
27             vector_score.push_back(score);
28             m[name]=score;
29             i++;
30         }
31     sort(vector_score.begin(),vector_score.end());
32   //     printf("v size%d",vector_score.size());
33    //     printf("m size%d",m.size());
34     if(mode==1)
35     {
36          for(int i=0;i<vector_score.size();i++)
37         {
38             for(auto iter=m.begin();iter!=m.end();iter++)
39             {
40                 if(iter->second==vector_score[i])
41                 {
42                     cout<<iter->first<<" "<<vector_score[i]<<endl;
43                     m.erase(iter->first);
44                     iter=m.begin();
45                     break;
46                 }
47             }
48        }
49         m.clear();
50         vector_score.clear();
51     }
52     else if(mode==0)
53     {
54         for(int i=vector_score.size()-1;i>=0;i--)
55         {
56             for(auto iter=m.begin();iter!=m.end();iter++)
57             {
58                 if(iter->second==vector_score[i])
59                 {
60                     cout<<iter->first<<" "<<vector_score[i]<<endl;
61                     m.erase(iter->first);
62                     iter=m.begin();
63                     break;
64                 }
65             }
66        }
67          m.clear();
68         vector_score.clear();
69     }
70    }
71     
72   return 0;
73     
74 }

想通过vector元素的顺序来确定map中元素的顺序,但是依然是map自动排序了。

解决办法:使用稳定排序stable_sort,改进后的代码如下:

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <algorithm>
 5 //#include <unordered_map>
 6 using namespace std;
 7  
 8 bool cmp0(const pair<string,int> &a,const pair<string,int> &b)
 9 {
10     return a.second>b.second;
11 }
12  
13 bool cmp1(const pair<string,int> &a,const pair<string,int> &b)
14 {
15     return a.second<b.second;
16 }
17  
18 void mysort(int n,int flag)
19 {
20     //unordered_map<string,int> res;
21     vector<pair<string,int>> res(n);
22     for(int i=0;i<n;i++)
23     {
24         cin>>res[i].first>>res[i].second;
25     }
26     if(flag==0)
27     {
28         stable_sort(res.begin(),res.end(),cmp0);
29     }
30     else if(flag==1)
31     {
32         stable_sort(res.begin(),res.end(),cmp1);
33     }
34  
35     for(int i=0;i<n;i++)
36     {
37         cout<<res[i].first<<" "<<res[i].second<<endl;
38     }
39 }
40  
41 int main()
42 {
43     int n,flag;
44     while(cin>>n>>flag)
45     {
46         mysort(n,flag);
47     }
48     return 0;
49 }

总结:这个程序言简意赅,非常高效,值得借鉴和学习。pair这个结构作用挺好,对vector和map都适用,注意它的用法。

上一篇:【个人服务器】二、CentOS7.6服务器搭建Java相关环境


下一篇:TamronOS IPTV系统 ping 任意命令执行漏洞