【PAT甲级】排序题专题复习

深藏阁楼爱情的钟 2023-02-28 04:29 72阅读 0赞

### 固定模式 ###

要排序的量一般放在一个或多个向量的结构体、unordered\_map或者set中，然后定义一个或多个cmp函数。（具体是几个就看题目将排序对象分成几种、有几个判断依据）。

### 坑点 ###

1.最好直接用unordered\_map代替map，就不会有查询超时  
2.题目的要求都会有测试点，所以要好好读题，归纳出每种情况，想好再写，代码的复杂度其实不高的

### 普通题库（1001-1136） ###

*  [1012 The Best Rank (25)][1012 The Best Rank _25]  
    因为科目是固定的，而且要经过多次排序，就直接定义好数组方便访问：
    
        struct node { 
            int id, best;     
            int score[4], rank[4]; 
        }stu[2005];
 *  [1025 PAT Ranking (25)][1025 PAT Ranking _25]
    
        //10位数以内可以用int，长了就用long long
        
        //搞排名的时候，可以先写定第一项，后面的靠判断：
        v[0].locarank = 1;
        fin.push_back(v[0]);
        for(int j = 1; j < m; j++) {
             v[j].locarank = (v[j].score == v[j - 1].score) ? (v[j - 1].locarank) : (j + 1);
             fin.push_back(v[j]);
        }
        
        //考生编号可能前头有0，0也要要输出：
        %013lld //输出long long格式的数"
 *  [1028 List Sorting (25)][1028 List Sorting _25]
    
    技巧：不要用string，原理上的解释我查不到，只知道姓名长度不同，比到短的就退了。测试结果是没有规律的，真的不能用。
    
        char name[20];
        //不降序输出人名，strcmp就是ascii码左减右
        if(strcmp(a.name, b.name) == 0) 
            return a.no < b.no;
        return strcmp(a.name, b.name) <= 0;
 *  [1036 Boys vs Girls (25)][1036 Boys vs Girls _25]
 *  [1038 Recover the Smallest Number (30)][1038 Recover the Smallest Number _30]
    
        //排序的时候，需要考虑0的存在，即03和2组成的，是032小于203：
        bool cmp0(string a, string b) {
            return a + b < b + a; 
        }
        //但不要输出0：
        while(s.length() != 0 && s[0] == '0')
             s.erase(s.begin()); 
        if(s.length() == 0) cout << 0; 
        cout << s;
 *  [1062 Talent and Virtue (25)][1062 Talent and Virtue _25]
 *  [1075 PAT Judge (25)][1075 PAT Judge _25]
 *  [1083 List Grades (25)][1083 List Grades _25]

### 真题题库（近三年） ###

*  [1137 Final Grading (25)][1137 Final Grading _25]
 *  [1141 PAT Ranking of Institutions (25)][1141 PAT Ranking of Institutions _25] 
 *  [1153 Decode Registration Card of PAT (25)][1153 Decode Registration Card of PAT _25]
 *  [1157 Anniversary (25)][1157 Anniversary _25]

[1012 The Best Rank _25]: https://blog.csdn.net/liuchuo/article/details/52202171
[1025 PAT Ranking _25]: http://log.csdn.net/liuchuo/article/details/52188092
[1028 List Sorting _25]: https://blog.csdn.net/liuchuo/article/details/52144549
[1036 Boys vs Girls _25]: https://blog.csdn.net/liuchuo/article/details/52119127
[1038 Recover the Smallest Number _30]: https://blog.csdn.net/liuchuo/article/details/52264827
[1062 Talent and Virtue _25]: https://blog.csdn.net/liuchuo/article/details/52122102
[1075 PAT Judge _25]: https://blog.csdn.net/liuchuo/article/details/52226005
[1083 List Grades _25]: https://blog.csdn.net/liuchuo/article/details/52146657
[1137 Final Grading _25]: https://blog.csdn.net/allisonshing/article/details/104355181
[1141 PAT Ranking of Institutions _25]: https://blog.csdn.net/allisonshing/article/details/104343852
[1153 Decode Registration Card of PAT _25]: https://blog.csdn.net/allisonshing/article/details/104326246
[1157 Anniversary _25]: https://blog.csdn.net/allisonshing/article/details/104274669