华为 · 排序 · 算法编程题
华为 排序 n ≤ 200 时限 1 秒 / 32 MB

题目描述

对于给出的 n 条姓名和成绩信息，根据指定的排序方式按成绩升序或降序排列并输出。
特别的，成绩相同的同学需要保持输入的先后顺序进行排序。可能存在多条信息的学生姓名一致。

输入输出

输入描述
第一行输入一个整数 n (1 ≤ n ≤ 200) 代表学生人数。
第二行输入一个整数 op (0 ≤ op ≤ 1) 代表排序方式，其中， 0 表示按成绩降序， 1 表示按成绩升序。
此后 n 行，第 i 行依次输入：
一个长度为 1 ≤ len(s_i) ≤ 20 、由大小写字母构成的字符串 s_i 代表第 i 个学生的姓名；
一个整数 a_i (0 ≤ a_i ≤ 100) 代表这个学生的成绩。
输出描述
根据输入的排序方式，按照成绩升序或降序输出所有学生的姓名和成绩。对于每一名学生，新起一行。输出学生的姓名和成绩，用空格分隔。

样例共 2 组

样例 1 · 在这个样例中， op = 0 ，因此按成绩降序排序。
输入
3
0
fang 90
yang 50
ning 70
输出
fang 90
ning 70
yang 50
样例 2 · 在这个样例中， op = 1 ，因此按成绩升序排序。
输入
4
1
fang 90
yang 50
ning 70
yang 70
输出
yang 50
ning 70
yang 70
fang 90

算法解析依据充分

考点：排序

数据规模 n ≤ 200 ｜ 限制 1 秒 / 32MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 200
  • 元素值域：a_i ≤ 100，s_i ≤ 20（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：排序

先用 O(n log n) 排序把无序变有序，后续处理往往就简单了。

思路框架（排序 通法 · 非本题专属）

  1. 排序后很多性质变简单：相邻关系、前缀性质、二分可行。
  2. 若题目禁止使用排序库函数，则手写快排/归并（归并还能顺带求逆序对）。
  3. 排序常与其他范式组合，比如「排序 + 贪心」「排序 + 二分」「排序 + 双指针」。

实现要点：在 C++ 中用 std::sort，Python 用 sorted()；注意自定义比较函数的严格弱序。

复杂度：时间 O(n log n) ｜ 空间 O(log n) ~ O(n)

该范式的通法易错点

  • 自定义比较函数不满足严格弱序会导致运行时崩溃。
  • 排序后丢失原始下标，题目需要下标时记得用 pair 一起排。

对照本题

  • 数据规模 n ≤ 200，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 100 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 / 0 / fang 90 / yang 50 / ning 70 → 输出 fang 90 / ning 70 / yang 50

在这个样例中， op = 0 ，因此按成绩降序排序。

样例 2：输入 4 / 1 / fang 90 / yang 50 / ning 70 / yang 70 → 输出 yang 50 / ning 70 / yang 70 / fang 90

在这个样例中， op = 1 ，因此按成绩升序排序。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：华为机试编程模拟题7。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解