开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> PAT甲级刷题记录-(AcWing)-(Day04排序) -> 正文阅读

[C++知识库]PAT甲级刷题记录-(AcWing)-(Day04排序)

PAT甲级刷题记录-(AcWing)-(Day04排序)

课程来源AcWing
其中AcWing中的题目为翻译好的中文题目

今日刷题列表

1012 The Best Rank
1022 Digital Library
1025 PAT Ranking
1028 List Sorting
1039 Course List for Student
1052 Linked List Sorting
1075 PAT Judge
1098 Insertion or Heap Sort

1012 The Best Rank

AcWing链接
 PAT链接

英语单词

evaluate 评估评价
At the mean time 与此同时
with respect to 关于

解析

使用map来存储学生的信息
分别对每个成绩建立一个vecor 对其排序,在查询学生成绩的时候在排好序的vector里面找排名。
这边的查找排名也可以用二分查找来做,可能更快一点

注意点

我第一次做题的时候用了int rank = n + 1; 本来是想让rank初试为一个最大数的,但是忘了之前while(n--)的时候已经把n搞成0了,这里卡了半天,后来终于找到了
这道题AcWing的测试点比PAT上准一点, 在求grade的时候我写了round(A / 3)在PAT上也过了, 但是在AcWing上没过, 错误案例如下, 应该用round(A / 3.0)才行。
测试用例

100 1
135431 4 73 15
368745 43 94 38
201256 51 71 91
330141 36 32 85
716013 16 91 71
769920 45 2 60
511204 68 86 20
898775 49 53 14
112884 55 36 1
776469 29 54 38
738731 89 30 79
907419 71 17 58
383651 60 11 36
426729 23 99 32
503408 29 88 88
415325 29 31 57
164362 90 99 96
865207 39 43 95
745915 85 74 67
326962 36 26 46
848993 7 40 11
289416 27 36 15
704145 63 46 95
697517 10 56 82
886800 49 83 67
518567 54 9 20
158371 31 11 31
426712 58 52 8
768560 57 26 54
147783 58 29 35
900145 76 66 74
811907 56 32 91
117719 92 32 43
869277 17 9 3
507275 54 25 44
777986 50 49 76
763103 79 45 8
547321 74 38 35
385514 79 71 31
276025 51 57 1
734645 62 43 86
341135 26 9 79
474150 18 4 22
361938 57 75 18
374423 58 69 3
198468 84 50 33
362674 23 52 3
391470 62 70 36
133655 96 62 73
527967 73 64 28
469313 57 88 10
878081 9 49 38
604614 63 23 41
217877 4 63 17
435030 15 66 46
211277 26 86 60
186493 55 85 3
616715 87 13 90
916960 11 75 28
611032 5 60 74
500081 61 28 27
763375 91 24 73
104276 4 90 76
212765 33 89 32
796626 76 47 54
380053 46 31 22
155429 80 99 45
716284 70 89 31
671732 6 84 51
648859 9 20 55
914689 93 96 80
375198 66 37 88
590224 56 6 60
313037 79 65 38
508622 56 18 75
983349 44 0 15
479853 59 54 23
274852 12 34 44
490099 27 81 52
427390 91 75 37
823659 24 33 4
989022 90 90 8
882082 15 62 47
218210 73 49 78
760582 70 80 10
682419 32 37 45
953690 23 80 92
879559 61 39 41
499622 13 82 87
377547 88 0 32
916659 33 95 56
883351 35 35 69
760773 10 98 81
855530 45 42 32
148220 47 43 19
140953 22 94 18
466785 91 58 8
770231 19 83 33
198004 54 40 55
802080 6 67 62
886800

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>

using namespace std;
map<string, vector<int>> students;
vector<int> grade[4];

int get_rank(int score, int idx) {
    int res = 0;
    vector<int> course = grade[idx];
    if (score == course[0]) return 1;
    int rank = 1;
    // 找score在course中的排名, 其中course已经排好序
    for (int i = 1; i < course.size(); ++i) {
        if (course[i] < course[i - 1])
            rank = i + 1;
        if (score == course[i])
            return rank;
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    while (n--) {
        string id;
        int score[4];
        int A = 0;
        cin >> id;
        for (int i = 1; i < 4; ++i) {
            cin >> score[i];
            A += score[i];
        }
        score[0] = round(A / 3.0);
        for (int i = 0; i < 4; ++i) {
            grade[i].push_back(score[i]);
            students[id].push_back(score[i]);
        }
    }
    for (int i = 0; i < 4; ++i)
        sort(grade[i].begin(), grade[i].end(), greater<int>());
    while (m--) {
        string id;
        cin >> id;
        if (students.count(id) == 0) puts("N/A");
        else {
            int rank = students.size() + 1;
            int res;
            string names = "ACME";
            vector<int> cur_scores = students[id];
            for (int i = 0; i < 4; ++i) {
                int cur_rank = get_rank(cur_scores[i], i);
                if (cur_rank < rank) {
                    rank = cur_rank;
                    res = i;
                }
            }
            cout << rank << " " << names[res] << endl;
        }
    }
    return 0;
}

1022 Digital Library

AcWing链接
 PAT链接

英语单词

is assigned 被分配
any query 任何疑问

解析

主要是选择合适的存储方式
仔细的根据各个点来输出
注意点
在创建结构体的时候用set来存keywords, 可以在查询的时候使用cout方法来确定是否存在(本题的输入中只包含一个关键词,也就是一个单词)
cin和getline之间一定要加getchar(), 我在这边卡了一些时间.

第一次的答案(能通过PAT,但是在AcWing上会超时)

#include <iostream>
#include <cstdio>
#include <vector>
#include <sstream>
#include <algorithm>
#include <set>

using namespace std;
struct Book {
    string id, title, author, publisher;
    set<string> keywords;
    int year;
} books[10010];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string id, title, author, publisher;
        set<string> keywords;
        int year;
        cin >> id;
        getchar();
        getline(cin, title);
        getline(cin, author);
        string line;
        getline(cin, line);
        stringstream ssin(line);
        string word;
        while (ssin >> word) keywords.insert(word);
        getline(cin, publisher);
        cin >> year;
        books[i] = {id, title, author, publisher, keywords, year};
    }
    int m;
    cin >> m;
    getchar();
    while (m--) {
        string line;
        getline(cin, line);
        puts(line.c_str());
        vector<string> res;
        if (line[0] == '1')
            for (auto &book:books)
                if (book.title == line.substr(3))
                    res.push_back(book.id);
        if (line[0] == '2')
            for (auto &book:books)
                if (book.author == line.substr(3))
                    res.push_back(book.id);
        if (line[0] == '3') {
            for (auto &book:books)
                if (book.keywords.count(line.substr(3)))
                    res.push_back(book.id);
        }
        if (line[0] == '4')
            for (auto &book:books)
                if (book.publisher == line.substr(3))
                    res.push_back(book.id);
        if (line[0] == '5')
            for (auto &book:books)
                if (to_string(book.year) == line.substr(3))
                    res.push_back(book.id);
        if (res.empty()) cout << "Not Found" << endl;
        else {
            sort(res.begin(), res.end());
            for (int i = 0; i < res.size(); ++i) {
                cout << res[i] << endl;
            }
        }

    }
    return 0;
}

第二次的答案都能通过

#include <iostream>
#include <cstdio>
#include <vector>
#include <sstream>
#include <algorithm>
#include <set>

using namespace std;
struct Book {
    string id, title, author, publisher;
    set<string> keywords;
    string year;
};
vector<Book> books;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string id, title, author, publisher;
        set<string> keywords;
        string year;
        cin >> id;
        getchar();
        getline(cin, title);
        getline(cin, author);
        string line;
        getline(cin, line);
        stringstream ssin(line);
        string word;
        while (ssin >> word) keywords.insert(word);
        getline(cin, publisher);
        cin >> year;
        books.push_back({id, title, author, publisher, keywords, year});
    }
    int m;
    cin >> m;
    getchar();
    while (m--) {
        string line;
        getline(cin, line);
        puts(line.c_str());
        vector<string> res;
        string info = line.substr(3);
        if (line[0] == '1')
            for (auto &book:books)
                if (book.title == info)
                    res.push_back(book.id);
        if (line[0] == '2')
            for (auto &book:books)
                if (book.author == info)
                    res.push_back(book.id);
        if (line[0] == '3') {
            for (auto &book:books)
                if (book.keywords.count(info))
                    res.push_back(book.id);
        }
        if (line[0] == '4')
            for (auto &book:books)
                if (book.publisher == info)
                    res.push_back(book.id);
        if (line[0] == '5')
            for (auto &book:books)
                if (book.year == info)
                    res.push_back(book.id);
        if (res.empty()) cout << "Not Found" << endl;
        else {
            sort(res.begin(), res.end());
            for (int i = 0; i < res.size(); ++i) {
                cout << res[i] << endl;
            }
        }

    }
    return 0;
}

1025 PAT Ranking

AcWing链接
 PAT链接

英语单词

simultaneously 同时的

解析

注意点

在计算区域排名的时候卡了一会,这里的做法是创建一个vector<Student> local[110];数组来先计算学生的区域成绩,然后一个个插入到vector<Student> students(总学生榜)中,最后对总的学生计算他们的总排名

我的解答

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Student {
    string id;
    int grade;
    int location;
    int local_rank;
    int final_rank;

    bool operator<(const Student &s) {
        if (grade != s.grade) return grade > s.grade;
        return id < s.id;
    }
};

vector<Student> local[110];
vector<Student> students;

int main() {
    int n, k;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> k;
        string id;
        int grade;
        for (int j = 0; j < k; ++j) {
            cin >> id >> grade;
            local[i].push_back({id, grade, i});
        }
        auto &s = local[i];
        sort(s.begin(), s.end());
        for (int j = 0; j < s.size(); ++j) {
            if (!j || s[j].grade < s[j - 1].grade) s[j].local_rank = j + 1;
            else s[j].local_rank = s[j - 1].local_rank;
            students.push_back(s[j]);
        }
    }


    cout << students.size() << endl;
    sort(students.begin(), students.end());

    for (int i = 0; i < students.size(); ++i) {
        if (!i || students[i].grade < students[i - 1].grade)
            students[i].final_rank = i + 1;
        else
            students[i].final_rank = students[i - 1].final_rank;
    }
    for (auto &s:students) {
        cout << s.id << " " << s.final_rank << " " <<
             s.location << " " << s.local_rank << endl;
    }
    return 0;
}

1028 List Sorting

AcWing链接
 PAT链接

英语单词

imitate 模仿

解析

主要使用自定义排序方式对结构体进行排序
一般题目里面出现了 $10^5$ 数量级就用scanf和printf比较稳妥

我的方法(PAT通过,AcWing超时)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

struct Records {
    string id;
    string name;
    int grade;
};
int c;

bool cmp(Records r1, Records r2) {
    if (c == 1) {
        return r1.id < r2.id;
    } else if (c == 2) {
        if (r1.name != r2.name) return r1.name < r2.name;
        return r1.id < r2.id;
    } else {
        if (r1.grade != r2.grade) return r1.grade < r2.grade;
        return r1.id < r2.id;
    }
}

int main() {
    int n;
    cin >> n >> c;
    vector<Records> records;
    for (int i = 0; i < n; ++i) {
        string id, name;
        int grade;
        cin >> id >> name >> grade;
        records.push_back({id, name, grade});
    }
    sort(records.begin(), records.end(), cmp);
    for (int i = 0; i < records.size(); ++i) {
        cout << records[i].id << " " << records[i].name << " " << records[i].grade << endl;
    }
    return 0;
}

把所有的cin,cout换为scanf和printf就能在两边都通过了

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

struct Records {
    string id;
    string name;
    int grade;
};
int c;

bool cmp(Records r1, Records r2) {
    if (c == 1) {
        return r1.id < r2.id;
    } else if (c == 2) {
        if (r1.name != r2.name) return r1.name < r2.name;
        return r1.id < r2.id;
    } else {
        if (r1.grade != r2.grade) return r1.grade < r2.grade;
        return r1.id < r2.id;
    }
}

int main() {
    int n;
    scanf("%d %d", &n, &c);
    vector<Records> records;
    for (int i = 0; i < n; ++i) {
        char id[10], name[10];
        int grade;
        scanf("%s %s %d", id, name, &grade);
        records.push_back({id, name, grade});
    }
    sort(records.begin(), records.end(), cmp);
    for (int i = 0; i < records.size(); ++i) {
        printf("%s %s %d\n",records[i].id.c_str(),records[i].name.c_str(), records[i].grade);
    }
    return 0;
}

1039 Course List for Student

AcWing链接
 PAT链接

英语单词

解析

思路较为简单,在输入课程的同时按学生姓名来存储选的课程

在查询学生课程那边我使用stringstream作为输入产生了一些问题,后来换了之后就对了,没仔细研究哪里的问题

使用map只能在PAT上通过,使用unordered_map则两边都能过

#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

unordered_map<string, vector<int>> records;

int main() {
    int n, k;
    cin >> n >> k;
    while (k--) {
        int c_id, t;
        cin >> c_id >> t;
        for (int i = 0; i < t; ++i) {
            string name;
            cin >> name;
            records[name].push_back(c_id);
        }
    }
    while (n--) {
        string name;
        cin >> name;
        auto &stu = records[name];
        if (stu.empty()) cout << name << " 0" << endl;
        else {
            sort(stu.begin(), stu.end());
            cout << name << " " << stu.size();
            for (auto x:stu) {
                cout << " " << x;
            }
            cout << endl;
        }
    }
    return 0;
}

1052 Linked List Sorting

AcWing链接
 PAT链接

英语单词

adjacent 临近

解析
使用vector来代替传统的链表完成排序操作

注意点

注意本题不能用cin
注意当链表为空的时候要输出0 -1

#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    string address;
    int value;
    string next;
};
unordered_map<string, Node> list;

bool cmp(Node n1, Node n2) {
    return n1.value < n2.value;
}

int main() {
    int N;
    char head[10];
    scanf("%d %s", &N, head);
    while (N--) {
        char address[10], next[10];
        int value;
        scanf("%s %d %s", address, &value, next);
        list[address] = {address, value, next};
    }
    vector<Node> nodes;
    for (string i = head; i != "-1"; i = list[i].next)nodes.push_back(list[i]);
    if (nodes.size() == 0) printf("0 -1\n");
    else {
        sort(nodes.begin(), nodes.end(), cmp);
        printf("%d %s\n", nodes.size(), nodes[0].address.c_str());
        for (int i = 0; i < nodes.size(); ++i) {
            if (i < nodes.size() - 1)
                printf("%s %d %s\n", nodes[i].address.c_str(), nodes[i].value, nodes[i + 1].address.c_str());
            else
                printf("%s %d -1\n", nodes[i].address.c_str(), nodes[i].value);
        }

    }

    return 0;
}

1075 PAT Judge

AcWing链接
 PAT链接

英语单词

submissions 提交

解析

注意点
这里用到了结构体内部定义函数,用法和类和对象差不多
结构体初始化函数格式


struct Student {
	Student(){};
    Student(string id) : s_id(id) {...}
}

我的答案

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
int n, k, m;
int perfect[6];

struct Student {
    string s_id;
    int grade[6]; // 每道题的分数
    int total, cnt;// 所有题的总分和满分的数量
    Student() {};

    Student(string id) : s_id(id) {
        for (int i = 0; i < k; ++i) {
            grade[i] = -2;
            total = cnt = 0;
        }
    }

    void cal() {
        for (int i = 0; i < k; ++i) {
            if (grade[i] >= 0) {
                total += grade[i];
                if (grade[i] == perfect[i]) cnt++;
            }
        }
    }

    bool is_submit() {
        int s = 0;
        for (int i = 0; i < k; ++i) {
            if (grade[i] >=0) return true;
        }
        return false;
    }

    bool operator<(const Student &t) {
        if (total != t.total)return total > t.total;
        if (cnt != t.cnt)return cnt > t.cnt;
        return s_id < t.s_id;
    }
};

int main() {
    cin >> n >> k >> m;
    for (int i = 0; i < k; ++i)cin >> perfect[i];
    unordered_map<string, Student> map;
    while (m--) {
        string s_id;
        int q_idx, grade;
        cin >> s_id >> q_idx >> grade;
        if (map.count(s_id) == 0)map[s_id] = Student(s_id);
        map[s_id].grade[q_idx - 1] = max(grade, map[s_id].grade[q_idx - 1]);
    }
    vector<Student> students;
    for (auto &item:map) {
        auto stu = item.second;
        if (stu.is_submit()) {
            stu.cal();
            students.push_back(stu);
        }
    }
    sort(students.begin(), students.end());
    int rank = 1;
    for (int i = 0; i < students.size(); ++i) {
        if (!i || students[i].total < students[i - 1].total) rank = i + 1;
        cout << rank << " " << students[i].s_id
             << " " << students[i].total;
        for (int j = 0; j < k; ++j) {
            int g = students[i].grade[j];
            if (g == -2)
                cout << " -";
            else
                cout << " " << max(0, g);
        }
        cout << endl;

    }
    return 0;
}

1098 Insertion or Heap Sort

AcWing链接
 PAT链接

注意点
这边还是要补一下堆排序和插入排序的知识
注意堆排序为了让下标能够正确的表示子孙,需要从1开始存

#include <iostream>

const int N = 101;
using namespace std;
int a[N], b[N]; //a为原序列 b为迭代后的序列

void down(int u, int size) {
    int t = u;
    if (u * 2 <= size && b[t] < b[u * 2])t = u * 2;
    if (u * 2 + 1 <= size && b[t] < b[u * 2 + 1]) t = u * 2 + 1;
    if (t != u) {
        swap(b[t], b[u]);
        down(t, size);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    int k = 1;
    for (int i = 2; i <= n; ++i) {
        if (b[i] < b[i - 1]) {
            k = i;
            break;
        }
    }
    int i;
    for (i = k; i <= n; ++i) {
        if (b[i] != a[i])break;
    }
    if (i == n + 1) {
        cout << "Insertion Sort" << endl;
        for (int j = k; j >= 2; j--) {
            if (b[j] < b[j - 1])
                swap(b[j], b[j - 1]);
            else
                break;
        }
        for (int j = 1; j <= n; ++j) {
            if (j==1) cout << b[j];
            else cout << " " << b[j];
        }

    } else {
        cout << "Heap Sort" << endl;
        // 找后面几个有序的数字
        int p = n;
        while (b[1] <= b[p]) p--;
        swap(b[1], b[p]);
        down(1, p - 1);
        for (int j = 1; j <= n; ++j) {
            if (j==1) cout << b[j];
            else cout << " " << b[j];
        }
    }


    return 0;
}