算法
(排序,多关键字排序) $O(nlogn)$
多关键字排序即可。
时间复杂度
这里使用快速排序,时间复杂度是 $O(nlogn)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
struct Person
{
int chinese, math, english;
int total;
int id;
bool operator< (const Person& W)const
{
if (total != W.total) return total > W.total;
if (chinese != W.chinese) return chinese > W.chinese;
return id < W.id;
}
}person[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
int chinese, math, english;
scanf("%d%d%d", &chinese, &math, &english);
int total = chinese + math + english;
person[i] = {chinese, math, english, total, i};
}
sort(person + 1, person + 1 + n);
for (int i = 1; i <= 5; i ++ ) printf("%d %d\n", person[i].id, person[i].total);
return 0;
}