题解 | 成绩排序

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

class Student {
  public:
    string name;
    int mark;
};

//需要一个稳定的排序算法

void my_merge(int l, int mid, int r, vector<Student>& v, int way) {
    vector<Student> tmp;
    // cout << l << mid << r << endl;
    int i = l, j = mid + 1;
    if (way == 0) {
        while (i <= mid && j <= r) {
            if (v[i].mark >= v[j].mark)
                tmp.push_back(v[i++]);
            else
                tmp.push_back(v[j++]);
        }
    } else {
        while (i <= mid && j <= r) {
            if (v[i].mark <= v[j].mark)
                tmp.push_back(v[i++]);
            else
                tmp.push_back(v[j++]);
        }
    }

    while (i <= mid) tmp.push_back(v[i++]);
    while (j <= r) tmp.push_back(v[j++]);
    // for (int i = l; i <= r ; i++)
    //     cout << tmp[i - l].name << endl;
    for (int i = l; i <= r; i++) {
        v[i] = tmp[i - l];
    }
}

void merge_sort(int l, int r, vector<Student>& v, int way) {
    if (l < r) {
        int mid = (l + r) / 2;
        merge_sort(l, mid, v, way);
        merge_sort(mid + 1, r, v, way);
        my_merge(l, mid, r, v, way);
    }
}

int main() {
    int a, way;
    while (cin >> a >> way) {
        vector<Student> stus;
        for (int i = 0; i < a; i++) {
            Student temp;
            cin >> temp.name >> temp.mark;
            stus.push_back(temp);
        }
        merge_sort(0, stus.size() - 1, stus, way);

        for (Student x : stus) {
            cout << x.name << ' ' << x.mark << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")