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

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

固定模式

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

坑点

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

普通题库（1001-1136）

  • 1012 The Best Rank (25)
    因为科目是固定的，而且要经过多次排序，就直接定义好数组方便访问：

    1. struct node {

    2.     int id, best;

    3.     int score[4], rank[4];

    4. }stu[2005];

  • 1025 PAT Ranking (25)

    1. //10位数以内可以用int，长了就用long long
    3. //搞排名的时候，可以先写定第一项，后面的靠判断：
    4. v[0].locarank = 1;
    5. fin.push_back(v[0]);
    6. for(int j = 1; j < m; j++) {
    7.      v[j].locarank = (v[j].score == v[j - 1].score) ? (v[j - 1].locarank) : (j + 1);
    8.      fin.push_back(v[j]);
    9. }
    11. //考生编号可能前头有0，0也要要输出：
    12. %013lld //输出long long格式的数"

  • 1028 List Sorting (25)

    技巧：不要用string，原理上的解释我查不到，只知道姓名长度不同，比到短的就退了。测试结果是没有规律的，真的不能用。

    1. char name[20];
    2. //不降序输出人名，strcmp就是ascii码左减右
    3. if(strcmp(a.name, b.name) == 0) 
    4.     return a.no < b.no;
    5. return strcmp(a.name, b.name) <= 0;
  • 1036 Boys vs Girls (25)

  • 1038 Recover the Smallest Number (30)

    1. //排序的时候，需要考虑0的存在，即03和2组成的，是032小于203：
    2. bool cmp0(string a, string b)
{
    3.     return a + b < b + a;

    4. }
    5. //但不要输出0：
    6. while(s.length() != 0 && s[0] == '0')

    
s.erase(s.begin());


    1. if(s.length() == 0) cout << 0;

    2. cout << s;
  • 1062 Talent and Virtue (25)
  • 1075 PAT Judge (25)
  • 1083 List Grades (25)

真题题库（近三年）

  • 1137 Final Grading (25)
  • 1141 PAT Ranking of Institutions (25)
  • 1153 Decode Registration Card of PAT (25)
  • 1157 Anniversary (25)

发表评论

表情：
评论列表 （有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读

    相关 【PAT甲级】堆的专题复习

    虽然《算法笔记》的9.7有介绍堆，1098题也是跟堆有关。但是在PAT甲级近三年的题目里，没考过向下调整、建堆写法，只了解到堆的概念就行。目前的考纲也没有明确地提到“堆”。近三

    野性酷女野性酷女/ 0 赞/ 34 阅读

    相关 【PAT甲级】LCA专题复习

    这个部分在《算法笔记》是没有的。 这种新背景的题目，如果之前没有接触过，那只能从普通的定义去解，即： 1.建树 2.找祖先，找到一致的就是最低公共祖先 例子：[hih

    清疚清疚/ 0 赞/ 77 阅读