第4章 排序

1012. The Best Rank

笔记

• 按学科存储各个学生成绩，同时也按学号存储各个学生的成绩。排序后，再用二分查找学生某科成绩的排名
• 注意是从大到小排序，需要用sort(a.begin(), a.end(), greater<int>())
• 可用哈希表加快学生的查找，二分加快成绩的查找
• 实现预处理查询结果，也可加快查找

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;

vector<int> grades[4];       // 对应A, C, M, E
unordered_map<string, vector<int>> students;
unordered_map<string, pair<int, char>> results;

int get_rank(int grade, vector<int> all) {
    int l = -1, r = all.size();
    while(l + 1 != r) {
        int m = l + r >> 1;
        if (all[m] > grade) l = m;
        else r = m;
    }
    return r + 1;
}

int main() {
    int n, k;
    cin >> n >> k;

    string id;
    int a, c, m, e;
    for (int i = 0; i < n; i++) {
        cin >> id >> c >> m >> e;
        a = round((c + m + e) / 3.0);
        grades[0].push_back(a);
        grades[1].push_back(c);
        grades[2].push_back(m);
        grades[3].push_back(e);
        students[id].push_back(a);
        students[id].push_back(c);
        students[id].push_back(m);
        students[id].push_back(e);
    }

    for (int i = 0; i < 4; i++)
        sort(grades[i].begin(), grades[i].end(), greater<int>());

    // 预处理结果
    char names[5] = "ACME";
    for (auto student : students) {
        id = student.first;
        vector<int> grade = student.second;

        int best_rank = n + 1;
        char best_subject = '0';
        for (int i = 0; i < 4; i++) {
            int rank = get_rank(grade[i], grades[i]);   // 获取第i个科目的排名
            // cout << rank << endl;
            if (rank < best_rank) {
                best_rank = rank;
                best_subject = names[i];
            }
        }

        results[id] = {best_rank, best_subject};
    } 

    while(k--) {
        cin >> id;
        if (results.count(id) == 0) puts("N/A");
        else printf("%d %c\n", results[id].first, results[id].second);
    }

    return 0;
}

1022. Digital Library

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

struct book {
    string id, name, author;
    set<string> keywords;
    string publisher, year;
};

int main() {
    int n, m;
    cin >> n;
    getchar();

    string id, name, author, publisher, year, keyword, key;
    set<string> keywords;
    vector<book> books;
    for (int i = 0; i < n; i++) {
        keywords.clear();
        cin >> id;
        getchar();
        getline(cin, name);
        getline(cin, author);
        getline(cin, keyword);
        stringstream ssin(keyword);
        while (ssin >> key) keywords.insert(key);
        getline(cin, publisher);
        cin >> year;
        books.push_back({id, name, author, keywords, publisher, year});
    }

    cin >> m;
    getchar();
    string op, arg;
    while(m--) {
        cin >> op;
        getchar();
        getline(cin, arg);
        vector<string> res;
        if (op[0] == '1') {
            for (auto& item : books)
                if (item.name == arg)
                    res.push_back(item.id);
        } else if (op[0] == '2'){
            for (auto& item : books)
                if (item.author == arg)
                    res.push_back(item.id);
        } else if (op[0] == '3'){
            for (auto& item : books)
                if (item.keywords.count(arg))
                    res.push_back(item.id);
        } else if (op[0] == '4'){
            for (auto& item : books)
                if (item.publisher == arg)
                    res.push_back(item.id);
        } else {
            for (auto& item : books)
                if (item.year == arg)
                    res.push_back(item.id);
        }

        cout << op << " " << arg << endl;
        if (!res.size()) puts("Not Found");
        else {
            sort(res.begin(), res.end());
            for (auto item : res)
                cout << item << endl;
        }
    }

    return 0;
}

1025. PAT Ranking

笔记

• 为了让sort实现降序排序，需要重载operator>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;

struct Student {
    string id;
    int location_number;
    int grade, local_rank, final_rank;

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

vector<Student> grades[N];
vector<Student> all;

int main() {
    int n, k;
    cin >> n;

    string id;
    int grade;
    for (int i = 1; i <= n; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> id >> grade;
            grades[i].push_back({id, i, grade, 0, 0});
        }

        sort(grades[i].begin(), grades[i].end(), greater<Student>());

        for (int j = 0; j < k; j++) {
            if (!j || grades[i][j].grade != grades[i][j - 1].grade)
                grades[i][j].local_rank = j + 1;
            else
                grades[i][j].local_rank = grades[i][j - 1].local_rank;
            all.push_back(grades[i][j]);
        }
    }

    sort(all.begin(), all.end(), greater<Student>());
    for (int i = 0; i < all.size(); i++)
        if (!i || all[i].grade != all[i - 1].grade)
            all[i].final_rank = i + 1;
        else
            all[i].final_rank = all[i - 1].final_rank;

    cout << all.size() << endl;
    for (auto& s : all)
        printf("%s %d %d %d\n", s.id.c_str(), s.final_rank, s.location_number, s.local_rank);

    return 0;
}

1028. List Sorting

笔记

• 本题数据量较大，用cin和cout会TLE，因此需要用scanf和printf
  • 结构体中若使用string类型保存id和name，则在scanf需要先用一个char数组保存结果，然后再传入构造函数中，此时构造函数会自动把char数组转成string。因为不能用scanf把字符串直接赋给string变量，才需要借用一个char数组中转
  • 在用printf输出string类型变量时，需要调用变量的方法c_str()，例如printf("%s", s.c_str());
• 可自定义多个bool cmp()作为sort()的比较器

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

struct Student {
    string id;
    string name;
    int score;
} students[N];

bool cmp1(Student s1, Student s2) {
    return s1.id < s2.id;
}

bool cmp2(Student s1, Student s2) {
    if (s1.name != s2.name) return s1.name < s2.name;
    else return s1.id < s2.id;
}

bool cmp3(Student s1, Student s2) {
    if (s1.score != s2.score) return s1.score < s2.score;
    else return s1.id < s2.id;
}

int main() {
    int n, c;
    scanf("%d%d", &n, &c);

    char id[10], name[10];
    int score;
    for (int i = 0; i < n; i++) {
        scanf("%s%s%d", id, name, &score);  // 先用char数组保存
        students[i] = {id, name, score};    // 构造时char数组自动转成string类型
    }

    if (c == 1) sort(students, students + n, cmp1);
    else if (c == 2) sort(students, students + n, cmp2);
    else sort(students, students + n, cmp3);

    for (int i = 0; i < n; i++)
        printf("%s %s %d\n", students[i].id.c_str(), students[i].name.c_str(), students[i].score);

    return 0;
}

1039. Course List for Student

笔记

• 本题时间复杂度要求比较高，需要用ios::sync_with_stdio(false);和cin.tie(0);
  • ios::sync_with_stdio(false);的作用是让cin和cout绕开缓存，让c++避免为了兼容printf和scanf牺牲的速度，直接读写，提高速度，此时效率和scanf和printf相差无几
  • 在默认的情况下cin绑定的是cout，每次执行<<操作符的时候都要调用flush，增加IO负担。tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

unordered_map<string, vector<int>> students;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    int id, m;
    string name;
    while(k--) {
        cin >> id >> m;
        while(m--) {
            cin >> name;
            students[name].push_back(id);
        }
    }

    for (auto& student : students) {
        auto& grades = student.second;
        sort(grades.begin(), grades.end());
    }

    while(n--) {
        cin >> name;
        auto& grades = students[name];
        cout << name << " " << grades.size();
        for (int grade : grades)
            cout << " " << grade;
        cout << endl;
    }

    return 0;
}

1052. Linked List Sorting

笔记

• 排序时，不用真的在链表结构上排序，只需排序后再仿照链表结构输出即可

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

struct node {
    string address;
    int key;
    string next;

    bool operator< (const node& a) const {
        return key < a.key;
    }

} nodes[N];

unordered_map<string, node> all;

int main() {
    int n, key;
    char head[6], address[6], next[6];
    scanf("%d%s", &n, head);

    for (int i = 0; i < n; i++) {
        scanf("%s%d%s", address, &key, next);
        all[address] = {address, key, next};
    }

    n = 0;
    for (string p = head; p != "-1"; p = all[p].next)
        nodes[n++] = all[p];
    sort(nodes, nodes + n);


    if (n == 0) printf("0 -1\n");
    else {
        printf("%d %s\n", n, nodes[0].address.c_str());
        for (int i = 0; i < n; i++)
            if (i + 1 < n)
                printf("%s %d %s\n", nodes[i].address.c_str(), nodes[i].key, nodes[i + 1].address.c_str());
            else
                printf("%s %d -1\n", nodes[i].address.c_str(), nodes[i].key);
    }
    return 0;
}

1075. PAT Judge

笔记

• 每一道题分为三种状态
  • -2：未答题，记为0分，输出记为-
  • -1：编译错误，记为0分，输出为0
  • 0~max：得分，输出为其分值
• 每一个学生的答题情况分为两种情况
  • 所有题都没有答或者都没通过编译，排名时不考虑该学生
  • 只有答了1题或者有1道题目通过编译，排名时就要考虑该学生
• 在保存学生答题情况时，可用散列表unordered_map<string, Student>保存，由于value是结构体，因此在使用前需要判断该对象是否存在students.count(id) == 0，不存在需要调用Student的构造函数
• 在结构体新建有参构造函数时，需要显示声明一个无参构造函数，否则编译无法通过
• 题目本身不难，只是要注意的细节很多

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
const int K = 6;

int n, k, m;
int max_scores[K];       // 各题最高分

struct Student {
    string id;      // 编号
    int total;      // 总分
    int scores[K];   // 各题得分（-2表示未答题，-1表示编译不通过）
    int cnt;        // 满分题数

    Student(){}     // 在结构体新建有参构造函数时，需要显示声明一个无参构造函数！
    Student(string _id) : id(_id) 
    {
        for (int i = 1; i <= k; i++) scores[i] = -2;     // 默认未答题
        total = 0;
        cnt = 0;
    }

    void cal_sum() {
        for (int i = 1; i <= k; i++) {
            if (scores[i] > 0) total += scores[i];
            if (scores[i] == max_scores[i])
                cnt++;
        }
    }

    bool has_submit() {
        for (int i = 1; i <= k; i++)
            if (scores[i] >= 0)
                return true;
        return false;
    }
};

bool cmp(const Student& s1, const Student& s2) {
    if (s1.total != s2.total) return s1.total > s2.total;
    else if (s1.cnt != s2.cnt) return s1.cnt > s2.cnt;
    else return s1.id < s2.id;
}

int main() {
    scanf("%d%d%d", &n, &k, &m);

    for (int i = 1; i <= k; i++) 
        scanf("%d", &max_scores[i]);

    unordered_map<string, Student> students;   

    int p_id, score;
    while(m--) {
        char u_id[8];
        scanf("%s%d%d", u_id, &p_id, &score);

        string id = u_id;
        if (students.count(id) == 0) 
            students[id] = Student(id);// 不存在则新建
        students[id].scores[p_id] = max(students[id].scores[p_id], score);
    }

    vector<Student> res;
    for (auto& item : students) {
        Student& student = item.second;
        student.cal_sum();
        if (student.has_submit())
            res.push_back(student);
    }

    sort(res.begin(), res.end(), cmp);

    for (int i = 0, rank = 1; i < res.size(); i++) {
        if (i && res[i].total != res[i - 1].total) rank = i + 1;

        printf("%d %s %d", rank, res[i].id.c_str(), res[i].total);

        for (int j = 1; j <= k; j++) 
            if (res[i].scores[j] == -2)
                printf(" -");
            else if (res[i].scores[j] == -1)
                printf(" 0");
            else
                printf(" %d", res[i].scores[j]);
        printf("\n");
    }

    return 0;
}

1098. Insertion or Heap Sort

笔记

• 插入排序特点：左段有序，右段与原段对应元素一致
• 堆排序特点：右段有序，且右段任一元素均大于左段第1个元素（堆顶）

#include <iostream>
using namespace std;
const int N = 102;
int n, a[N], b[N];

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


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];        // 堆排序要求编号从1开始
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    int i = 2;
    while(i <= n && b[i - 1] <= b[i]) i++;
    int k = i;
    while(i <= n && a[i] == b[i]) i++;
    if (i == n + 1) {
        // 插入排序特点
        //b[1]~b[k-1]有序，b[k]~b[n]与a[k]~a[n]一致
        puts("Insertion Sort");
        while (k > 1 && b[k - 1] > b[k]) {
            swap(b[k - 1], b[k]);
            k--;
        }
    } else {
        // 堆排序
        puts("Heap Sort");
        int j = n;
        while (b[j] >= b[1]) j--;
        swap(b[1], b[j]);       // 最大元素输出
        down(1, j - 1);         // 调整堆结构
    }

    cout << b[1];
    for (int i = 2; i <= n; i++)
        cout << " " << b[i];
    cout << endl;

    return 0;
}

1089. Insert or Merge

笔记

• 参照《Insertion or Heap Sort》确定插入排序，然后用迭代版归并排序实现下一次迭代
• 注意在判断插入排序时，需要用<=，而不是<

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int n, a[N], b[N];

void print(int c[]) {
    string res;
    for (int i = 0; i < n; i++)
        res += to_string(c[i]) + ' ';
    res.pop_back();
    cout << res << endl;
}

bool check(int c[], int d[]) {
    for (int i = 0; i < n; i++)
        if (c[i] != d[i])
            return false;
    return true;
}

void merge_sort(int c[], int len) {
    for (int i = 0; i < n; i += len)
        sort(c + i, c + min(n, i + len));
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    int k = 0;
    while(k + 1 < n && b[k] <= b[k + 1]) k++;

    bool flag = true;       // 假设是插入排序
    for (int i = k + 1; i < n; i++)
        if (a[i] != b[i]) {
            flag = false;
            break;
        }

    if (flag) {
        puts("Insertion Sort");
        sort(b, b + k + 2);
        print(b);

    } else {
        puts("Merge Sort");

        int t = 1;
        while(!check(a, b)) {
            merge_sort(a, 1 << t);     // 调用一次归并算法
            t++;
        }

        // 再迭代一次才是结果
        merge_sort(a, 1 << t);    
        print(a);
    }

    return 0;
}