文章

【GESP】C++五级真题（结构体排序考点） luogu-B3968 [GESP202403 五级] 成绩排序

发表于
作者 OneCoder
次浏览 13 分钟阅读

GESP C++ 2024年3月五级真题，结构体排序考点，难度⭐⭐★☆☆，属于五级真题中比较简单的。洛谷难度等级普及−

luogu-B3930 [GESP202312 五级] 烹饪问题

题目要求

题目描述

有 $n$ 名同学，每名同学有语文、数学、英语三科成绩，你需要按照如下规则对所有同学的成绩从高到低排序：

  1. 比较总分，高者靠前；
  2. 如果总分相同，则比较语文和数学两科的总分，高者靠前；
  3. 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
  4. 如果仍相同，则二人并列。

你需要输出每位同学的排名，如遇 $x$ 人并列，则他们排名相同，并留空后面的 $x - 1$ 个名次。例如，有 $3$ 名同学并列第 $1$，则后一名同学自动成为第 $4$ 名。

输入格式

第一行一个整数 $N$，表示同学的人数。
接下来 $N$ 行，每行三个非负整数 $c_i, m_i, e_i$ 分别表示该名同学的语文、数学、英语成绩。

输出格式

输出 $N$ 行，按输入同学的顺序，输出他们的排名。
注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名。

输入输出样例 #1

输入 #1
1
2
3
4
5
6
7

6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0
输出 #1
1
2
3
4
5
6

1
3
4
4
2
6

说明/提示

  • 对 $30\%$ 的数据，$N \leq 100$，且所有同学总分各不相同。
  • 对全部的测试数据，保证 $2 \leq N \leq 10^4$，$0 \leq c_i, m_i, e_i \leq 150$。

题目分析

解题思路

核心思想：把“成绩排序”拆成“结构体多级排序 + 并列名次压缩”。

方案一（两次排序）

  1. 结构体存 $c_i,m_i,e_i$、总分 $s_i=c_i+m_i+e_i$ 与原始下标。
  2. 自定义比较器 $\text{cmp}$：
    \(\text{cmp}(a,b)=\begin{cases} a.s> b.s\\[2pt] a.s=b.s~\land~ (a.c+a.m)>(b.c+b.m)\\[2pt] a.s=b.s~\land~ (a.c+a.m)=(b.c+b.m)~\land~ \max(a.c,a.m)>\max(b.c,b.m) \end{cases}\)
  3. 排序后线性扫描：若 $\text{cmp}(i,i-1)$ 为真则同排名，否则 $\text{rank}_i=i$。
  4. 再按原始下标排序，顺序输出 $\text{rank}$。

方案二（排序+查找）

前三步与方案一完全相同，第 4 步改为对原始序号逐一线性查找对应 $\text{rank}$ 并输出。

复杂度：

  • 两次排序均为 $O(N\log N)$；
  • 排序+查找方案中，每次线性查找排名为 $O(N)$，共 $N$ 次，总耗时 $O(N^2)$，在 $N\le 10^4$ 时仍可接受；空间均为 $O(N)$。

示例代码

方法一、两次排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#include <iostream>
#include <algorithm>

// 学生结构体：存储成绩、原始序号及排名
struct Student {
    int total;    // 三科总分
    int chinese;  // 语文成绩
    int math;     // 数学成绩
    int english;  // 英语成绩
    int id;       // 原始输入序号（1-based）
    int rank;     // 计算出的最终排名

    // 默认构造函数，全部初始化为0
    Student() : total(0), chinese(0), math(0), english(0), id(0), rank(0) {}

    // 带参构造函数：根据序号和三科成绩初始化，并自动计算总分
    Student(int id, int chinese, int math, int english)
        : id(id), chinese(chinese), math(math), english(english),
          total(chinese + math + english) {}
};

// 排序比较函数：按题目规则降序排列
// 1. 总分高者优先
// 2. 总分相同时，语文+数学总分高者优先
// 3. 仍相同，则语文、数学两科最高分高者优先
// 4. 仍相同，保持原顺序（返回 true 表示不交换）
bool cmp(Student a, Student b) {
    if (a.total != b.total) {
        return a.total > b.total;
    }
    if (a.chinese + a.math != b.chinese + b.math) {
        return a.chinese + a.math > b.chinese + b.math;
    }
    int max_a = std::max(a.chinese, a.math);
    int max_b = std::max(b.chinese, b.math);
    if (max_a != max_b) {
        return max_a > max_b;
    }
    return true;
}

// 按原始序号升序比较，用于最后恢复输入顺序
bool cmp_id(Student a, Student b) {
    return a.id < b.id;
}

// 最大学生数常量，1e4+5 防止越界
const int MAX_N = 1e4 + 5;
// 全局数组，存储所有学生信息
struct Student students[MAX_N];

int main() {
    int N;
    std::cin >> N;  // 读取学生人数

    // 依次读入每位学生的三科成绩，并用带参构造初始化结构体
    for (int i = 1; i <= N; i++) {
        int chinese, math, english;
        std::cin >> chinese >> math >> english;
        Student student(i, chinese, math, english);
        students[i] = student;
    }

    // 按自定义规则降序排序，排名计算基于排序后数组
    std::sort(students + 1, students + N + 1, cmp);

    // 计算并列排名：若当前学生与前一名“相等”（cmp 返回 true），则同排名；否则排名等于当前下标
    for (int i = 1; i <= N; i++) {
        if (i == 1) {
            students[i].rank = 1;  // 第一名默认排名 1
            continue;
        }
        if (cmp(students[i], students[i - 1])) {
            // 当前学生“等于”前一名，沿用前一名排名
            students[i].rank = students[i - 1].rank;
        } else {
            // 否则排名等于当前位置
            students[i].rank = i;
        }
    }

    // 按原始输入序号重新排序，恢复输入顺序
    std::sort(students + 1, students + N + 1, cmp_id);

    // 按原始输入顺序输出每位学生的最终排名
    for (int i = 1; i <= N; i++) {
        std::cout << students[i].rank << std::endl;
    }
    return 0;
}

方法二、排序+查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <algorithm>
#include <iostream>

// 学生结构体：存储单科成绩、总分、输入序号及最终排名
struct Student {
    int total;    // 三科总分
    int chinese;  // 语文成绩
    int math;     // 数学成绩
    int english;  // 英语成绩
    int id;       // 输入时的原始序号（1-based）
    int rank;     // 计算出的最终排名

    // 默认构造函数，初始化所有成员为0
    Student() : total(0), chinese(0), math(0), english(0), id(0), rank(0) {}

    // 带参构造函数：根据输入序号和三科成绩初始化，并自动计算总分
    Student(int id, int chinese, int math, int english)
        : id(id),
          chinese(chinese),
          math(math),
          english(english),
          total(chinese + math + english) {}
};

// 最大学生数常量，1e4+5 防止越界
const int MAX_N = 1e4 + 5;
// 全局数组，存储所有学生信息
struct Student students[MAX_N];

// 排序比较函数：按题目规则降序排列
// 1. 总分高者优先
// 2. 总分相同时，语文+数学总分高者优先
// 3. 仍相同，则语文、数学两科最高分高者优先
// 4. 仍相同，保持原顺序（返回 true 表示不交换）
bool cmp(Student a, Student b) {
    if (a.total != b.total) {
        return a.total > b.total;
    }
    if (a.chinese + a.math != b.chinese + b.math) {
        return a.chinese + a.math > b.chinese + b.math;
    }
    int max_a = std::max(a.chinese, a.math);
    int max_b = std::max(b.chinese, b.math);
    if (max_a != max_b) {
        return max_a > max_b;
    }
    return true;
}

// 根据学生原始 id 查询其在排序后数组中的排名
// 线性扫描，返回对应 rank；若未找到返回 0（理论上不会触发）
int get_rank(int id, int N) {
    for (int i = 1; i <= N; i++) {
        if (students[i].id == id) {
            return students[i].rank;
        }
    }
    return 0;
}

int main() {
    int N;
    std::cin >> N;  // 读取学生人数

    // 依次读入每位学生的三科成绩，并用带参构造初始化结构体
    for (int i = 1; i <= N; i++) {
        int chinese, math, english;
        std::cin >> chinese >> math >> english;
        Student student(i, chinese, math, english);
        students[i] = student;
    }

    // 按自定义规则降序排序，排名计算基于排序后数组
    std::sort(students + 1, students + N + 1, cmp);

    // 计算并列排名：若当前学生与前一名“相等”（cmp 返回 true），则同排名；否则排名等于当前下标
    for (int i = 1; i <= N; i++) {
        if (i == 1) {
            students[i].rank = 1;  // 第一名默认排名 1
            continue;
        }
        if (cmp(students[i], students[i - 1])) {
            // 当前学生“等于”前一名，沿用前一名排名
            students[i].rank = students[i - 1].rank;
        } else {
            // 否则排名等于当前位置
            students[i].rank = i;
        }
    }

    // 按原始输入顺序输出每位学生的最终排名
    for (int i = 1; i <= N; i++) {
        std::cout << get_rank(i, N) << std::endl;
    }
    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
GESP, 五级
GESP C++ 排序 结构体
本文由作者按照 CC BY-NC-SA 4.0 进行授权