题解 | #成绩排序#

将姓名和成绩以pair的形式存入vector中，然后对于从大到小或从小到大的情况进行归并排序，最后输出即可。STL中的sort函数排序的结果可能会出现错误，因此自己写了两个归并排序算法。

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

void merageHigh(vector<pair<string, int>> & scores, int start1, int end1, int start2, int end2) {
    int count1 = start1;
    int count2 = start2;
    vector<pair<string, int>> temp;
    while (count1 <= end1 && count2 <= end2) {
        if (scores.at(count1).second >= scores.at(count2).second) {
            temp.push_back(scores.at(count1));
            count1++;
        } else {
            temp.push_back(scores.at(count2));
            count2++;
        }
    }
    if (count1 <= end1) {
        for (int i = count1; i <= end1; i++) {
            temp.push_back(scores.at(i));
        }
    } else if (count2 <= end2) {
        for (int i = count2; i <= end2; i++) {
            temp.push_back(scores.at(i));
        }
    }
    for (int i = start1; i <= end2; i++) {
        scores.at(i) = temp.at(i - start1);
    }
}

void sortHigh(vector<pair<string, int>> & scores, int start, int end) {
    if (start == end) {
        return;
    }
    int start1 = start;
    int end1 = (start + end) / 2;
    int start2 = end1 + 1;
    int end2 = end;
    sortHigh(scores, start1, end1);
    sortHigh(scores, start2, end2);
    merageHigh(scores, start1, end1, start2, end2);
}

void merageLow(vector<pair<string, int>> & scores, int start1, int end1, int start2, int end2) {
    int count1 = start1;
    int count2 = start2;
    vector<pair<string, int>> temp;
    while (count1 <= end1 && count2 <= end2) {
        if (scores.at(count1).second <= scores.at(count2).second) {
            temp.push_back(scores.at(count1));
            count1++;
        } else {
            temp.push_back(scores.at(count2));
            count2++;
        }
    }
    if (count1 <= end1) {
        for (int i = count1; i <= end1; i++) {
            temp.push_back(scores.at(i));
        }
    } else if (count2 <= end2) {
        for (int i = count2; i <= end2; i++) {
            temp.push_back(scores.at(i));
        }
    }
    for (int i = start1; i <= end2; i++) {
        scores.at(i) = temp.at(i - start1);
    }
}

void sortLow(vector<pair<string, int>> & scores, int start, int end) {
    if (start == end) {
        return;
    }
    int start1 = start;
    int end1 = (start + end) / 2;
    int start2 = end1 + 1;
    int end2 = end;
    sortLow(scores, start1, end1);
    sortLow(scores, start2, end2);
    merageLow(scores, start1, end1, start2, end2);
}

int main() {
    int n;
    int kind;
    cin >> n >> kind;
    string name;
    int score;
    vector<pair<string, int>> scores;
    for (int i = 0; i < n; i++) {
        cin >> name >> score;
        scores.push_back({name, score});
    }
    if (kind == 0) {
        sortHigh(scores, 0, scores.size() - 1);
    } else {
        sortLow(scores, 0, scores.size() - 1);
    }
    for (pair<string, int> person : scores) {
        cout << person.first << ' ' << person.second << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")