202403-成绩排序(luogu-B3968)

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

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

题目要求

题目描述

有 $n$ 名同学，每名同学有语文、数学、英语三科成绩，你需要按照如下规则对所有同学的成绩从高到低排序：
比较总分，高者靠前；
如果总分相同，则比较语文和数学两科的总分，高者靠前；
如果仍相同，则比较语文和数学两科的最高分，高者靠前；
如果仍相同，则二人并列。
你需要输出每位同学的排名，如遇 $x$ 人并列，则他们排名相同，并留空后面的 $x - 1$ 个名次。例如，有 $3$ 名同学并列第 $1$ ，则后一名同学自动成为第 $4$ 名。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0

输出 #1

说明/提示

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

题目分析

解题思路

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

方案一（两次排序）

结构体存 $c_i,m_i,e_i$ 、总分 $s_i=c_i+m_i+e_i$ 与原始下标。
自定义比较器 $\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}$
排序后线性扫描：若 $\text{cmp}(i,i-1)$ 为真则同排名，否则 $\text{rank}_i=i$ 。
再按原始下标排序，顺序输出 $\text{rank}$ 。

方案二（排序+查找）

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

复杂度：

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

示例代码

方法一、两次排序

#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;
}

方法二、排序+查找

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年11月2日

202312-烹饪问题(luogu-B3930)202403-B-smooth 数(luogu-B3969)