AcWing 3375. 成绩排序
原题链接
简单
作者:
KaiWings-X
,
2024-07-27 17:47:38
,
所有人可见
,
阅读 5
/* 归并排序 稳定*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, p;
//定义结构体数组,用于存储个人信息
struct Stu {
string name;
int grade;
}stu[N];
void merge_sort(int l, int r, int p)
{
if(l == r) return;
int mid = l + r >> 1;
merge_sort(l, mid, p);
merge_sort(mid + 1, r, p);
Stu tmp[r - l + 1]; // 辅助结构体数组,暂存排序后的子序列
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(p == 1)
{
if(stu[i].grade <= stu[j].grade) tmp[k++] = stu[i++];
else tmp[k++] = stu[j++];
}
if(p == 0)
{
if(stu[i].grade < stu[j].grade) tmp[k++] = stu[i++];
else tmp[k++] = 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()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> p;
for(int i = 0; i < n; i++) cin >> stu[i].name >> stu[i].grade;
merge_sort(0, n - 1, p);
if(p == 1) {
for(int i = 0; i < n; i++) cout << stu[i].name << " " << stu[i].grade << endl;
}
else
{
reverse(stu, stu + n);
for (int i = 0; i < n; i++) cout << stu[i].name << " " << stu[i].grade << endl;
}
return 0;
}