題目描述

查找和排序

題目：輸入任意（用戶，成績）序列，可以獲得成績從高到低或從低到高的排列,相同成績      都按先錄入排列在前的規則處理。

   例示：   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;}