华为机试在线训练-牛客网（32）成绩排序

题目描述

查找和排序

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

   例示：   jack      70   peter     96   Tom       70   smith     67

   从高到低  成绩               peter     96       jack      70       Tom       70       smith     67    

   从低到高

   smith     67  

   Tom       70       jack      70       peter     96      

输入描述:

输入多行，先输入要排序的人的个数，然后分别输入他们的名字和成绩，以一个空格隔开
输出描述:
按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开
输入例子:
30fang 90yang 50ning 70
输出例子:
fang 90ning 70yang 50就是个考察排序的问题，问题在于怎么存，第一反应应该是map<string,int>，但是此题并不合适，理由如下：
 map<string,int>不合适的原因在于stable_sort()要求随机访问的迭代器，map的迭代器不满足要求。有个间接的方法还是要把map元素拷贝到vector<pair<string,int> > 中再排-----请参考博文第4条：       http://blog.csdn.net/hechao3225/article/details/55099083   
所以，个人认为此题最好的存储容器应该是vector<pair<string,int> > ，然后题目要求根据pair<string,int>的第二个值升序或降序排列，所以需要重写compare()函数以供stable_sort()调用；
另外，我一直说的是stable_sort()而不是sort()。原因很简单，此题用例的标准输出是稳定排序过的：即排序前后不影响相同key的相对位置。        而STL的sort()底层使用的快排，是不稳定的。因此，应该调用stable_sort()。当你调用sort()排序后，OJ提示你的答案不完整时，说明最后两个相同值排序后相对位置发生了改变，所以OJ把后面的结果全部截掉，换stable_sort()后AC。
这应该是此题考察的另外一个点：稳定排序与不稳定排序。
OJ战场，细节决定成败。
完整AC的代码：
#include <iostream>#include <vector>#include <algorithm>using namespace std;int cmpByValue1(const pair<string,int> &x,const pair<string,int> &y){    return x.second>y.second;}int cmpByValue2(const pair<string,int> &x,const pair<string,int> &y){    return x.second<y.second;}int main(){    int n,dir;    string name;    int grade;    while(cin>>n>>dir){        vector<pair<string,int> > vec_grades;        for(int i=0;i<n;i++){            cin>>name>>grade;            vec_grades.push_back(make_pair(name,grade));        }        if(dir==0)            stable_sort(vec_grades.begin(),vec_grades.end(),cmpByValue1);//降序        else            stable_sort(vec_grades.begin(),vec_grades.end(),cmpByValue2);//升序        for(auto e:vec_grades){            cout<<e.first<<" "<<e.second<<endl;        }    }    return 0;}