华为 · 排序 · 算法编程题
华为 排序 N ≤ 1e5 时限 2 秒 / 256 MB

题目描述

小红维护容量为 K 的缓存。`ADD` 插入位置、分数以及两个四维向量；位置唯一且严格递增。插入后若容量超过 K ，立即淘汰分数最低的记录，分数相同时淘汰位置较小者，并输出淘汰位置。`QUERY` 按位置升序输出所有缓存记录。

输入输出

输入描述
第一行输入 K,N 。`ADD pos score` 后紧跟两行各 4 个浮点数；另一种操作为 `QUERY`。所有浮点数都恰有一位小数。
保证 1≤ K,N≤10^5 ，位置在 [0,10^9] 且严格递增，分数在 [0,1000] ；全部查询输出的缓存记录总数不超过 5×10^5 。
输出描述
触发淘汰时输出 `PRUNED pos`。查询时先输出记录数，再对每条记录输出三行：`pos score`、Key 向量、Value 向量。所有浮点数原样保留一位小数。

样例共 1 组

样例 1 · 每次超容后按分数与位置的二元组淘汰最小记录。
输入
3 7
ADD 0 5.0
1.0 2.0 3.0 4.0
0.1 0.2 0.3 0.4
ADD 1 2.0
2.0 2.0 2.0 2.0
0.5 0.5 0.5 0.5
ADD 2 8.0
3.0 3.0 3.0 3.0
0.9 0.9 0.9 0.9
QUERY
ADD 3 6.0
4.0 4.0 4.0 4.0
0.0 0.0 0.0 0.0
QUERY
ADD 4 9.0
5.0 5.0 5.0 5.0
1.0 1.0 1.0 1.0
输出
3
0 5.0
1.0 2.0 3.0 4.0
0.1 0.2 0.3 0.4
1 2.0
2.0 2.0 2.0 2.0
0.5 0.5 0.5 0.5
2 8.0
3.0 3.0 3.0 3.0
0.9 0.9 0.9 0.9
PRUNED 1
3
0 5.0
1.0 2.0 3.0 4.0
0.1 0.2 0.3 0.4
2 8.0
3.0 3.0 3.0 3.0
0.9 0.9 0.9 0.9
3 6.0
4.0 4.0 4.0 4.0
0.0 0.0 0.0 0.0
PRUNED 0

算法解析依据一般

考点：排序

数据规模 N ≤ 1e5 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：K ≤ 1e5，N ≤ 1e5
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：排序

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 3 7 / ADD 0 5.0 / 1.0 2.0 3.0 4.0 / 0.1 0.2 0.3 0.4 / ADD 1 2.0 / 2.0 2.0 2.0 2.0 / 0.5 0.5 0.5 0.5 → 输出 3 / 0 5.0 / 1.0 2.0 3.0 4.0 / 0.1 0.2 0.3 0.4 / 1 2.0 / 2.0 2.0 2.0 2.0 / 0.5 0.5 0.5 0.5 / 2 8.0 /

每次超容后按分数与位置的二元组淘汰最小记录。

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

本题来源：2026年-华为-07月15号AI岗。

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