AcWing 3375. 成绩排序

题目

题目链接3375. 成绩排序

思路

思路要求稳定排序或者特判的快排
写法一：写两个sort中的比较函数的参数cmp
写法二：直接在结构体中进行比较
写法三：归并排序

代码1：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1100;
int n, k;

struct student{
    string name;
    int score, id;
}stu[N];

bool cmp0(student a, student b){
    if(a.score != b.score) return a.score > b.score;
    else return a.id < b.id;
}

bool cmp1(student a, student b){
    if(a.score != b.score) return a.score < b.score;
    else return a.id < b.id;
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i ++) cin >> stu[i].name >> stu[i].score, stu[i].id = i;
    sort(stu, stu + n, k ? cmp1 : cmp0);
    for(int i = 0; i < n; i ++) cout << stu[i].name << ' ' << stu[i].score << endl;
}

代码2

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1100;
int n, k;

struct Node{
    int score, id;
    string name;
    bool operator< (const Node & a) const{
        if(score == a.score) return id < a.id;
        return k ? score < a.score : score > a.score;
    }
}stu[N];

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i ++) cin >> stu[i].name >> stu[i].score, stu[i].id = i;
    sort(stu, stu + n);
    for(int i = 0; i < n; i ++) cout << stu[i].name << ' ' << stu[i].score << endl;
}

代码3

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1100;

int n, t;

struct{
    string name;
    int score;
}stu[N], tmp[N];

void mergeSort(int l, int r){
    if(l >= r) return ;
    int mid = l + r >> 1;
    mergeSort(l, mid), mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        tmp[k ++] = ((t && stu[i].score <= stu[j].score) || (!t && stu[i].score >= stu[j].score)) ? 
        stu[i ++] : stu[j ++];
    }
    while(i <= mid) tmp[k ++] = stu[i ++];
    while(j <= r) tmp[k ++] = stu[j ++];
    for(int i = l, j = 0; i <= r; i ++, j ++) stu[i] = tmp[j];
}

int main(){
    cin >> n >> t;
    for(int i = 0; i < n; i ++) cin >> stu[i].name >> stu[i].score;
    mergeSort(0, n - 1);
    for(int i = 0; i < n; i ++) cout << stu[i].name << ' ' << stu[i].score << endl;
}

AcWing题解