2026 华为OD机试真题8月26日日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

有一批货物 A 会按顺序进入仓库，第 i 件货物的价格是 A[i]。

管理员会发起一组查询请求 B，对于第 j 次查询，你需要回答：在当前已经进入仓库的前 B[j] 件货物中，按价格从小到大排序后，第 j 位的价格是多少。

题目保证所有查询合法，也就是说在第 j 次查询时，当前货物数量不少于 j。

其中 1≤j≤B[j]≤5000，1≤A[i]≤1000000。

2026 华为OD机试真题8月26日日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

• 参数 1：整数 n，表示货物数量；
• 参数 2：整数 m，表示查询次数；
• 参数 3：一组货物价格的列表 A，其中元素 A[i] 表示货物的价格；
• 参数 4：一组查询指令列表 B，其中元素 B[j] 表示第 j 次查询的货物范围区间。

输出描述

一个数组，其中每个元素为查询列表 B 中，每次指令查询的价格结果。

示例1

输入

7
4
9,7,2,8,14,1,8
1,2,6,6

输出

[9,9,7,8]

说明

• 一共有 7 件货物依次进入仓库；价格依次为：9, 7, 2, 8, 14, 1, 8

• 一共有 4 次查询，查询发生的时间分别是：

  • 前 1、前 2、前 6、前 6 件货物进入后

• 注意：第 j 次查询，不是问“第几件货物”，而是问：当前已有的这些货物里，按价格从小到大排，第 j 位是多少。

• 第 1 次查询（B[j]=1）：

  • 此时前 1 件货物 = [9]，排序后 [9]。
  • 第 1 次查找第 1 位，答案：9。

• 第 2 次查询（B[j]=2）：

  • 此时前 2 件货物 = [9, 7]，排序后得到：[7, 9]。
  • 第 2 次查询要找第 2 位，答案：9。

• 第 3 次查询（B[j]=6）：

  • 此时前 6 件货物 = [9, 7, 2, 8, 14, 1]，排序后得到：[1, 2, 7, 8, 9, 14]。
  • 第 3 次查询要找第 3 位，答案：7。

• 第 4 次查询（B[j]=6）：

  • 此时前 6 件货物 = [9, 7, 2, 8, 14, 1]，排序后得到：[1, 2, 7, 8, 9, 14]。
  • 第 4 次查询要找第 4 位，答案：8。

示例2

输入

5
5
8,4,4,10,9
1,2,3,5,5

输出

[8,8,8,9,10]

说明

• 一共有 5 件货物，价格依次为：8, 4, 4, 10, 9

• 一共有 5 次查询，发生时机分别是：

  • 前 1、前 2、前 3、前 5、前 5 件货物进入之后

• 第 1 次查询（B[j]=1）：

  • 此时前 1 件货物 = [8]，排序后 [8]。
  • 找第 1 位，答案：8。

• 第 2 次查询（B[j]=2）：

  • 此时前 2 件货物 = [8, 4]，排序后 [4, 8]。
  • 找第 2 位，答案：8。

• 第 3 次查询（B[j]=3）：

  • 此时前 3 件货物 = [8, 4, 4]，排序后 [4, 4, 8]。
  • 找第 3 位，答案：8。

• 第 4 次查询（B[j]=5）：

  • 此时前 5 件货物全部进入 = [8, 4, 4, 10, 9]，排序后 [4, 4, 8, 9, 10]。
  • 找第 4 位，答案：9。

• 第 5 次查询（B[j]=5，与第 4 次查询时机相同）：

  • 此时还是前 5 件货物 = [4, 4, 8, 9, 10]。
  • 找第 5 位，答案：10。

解题思路

核心思想

第 j 次查询需要在前 B[j] 件货物中找到第 j 小的价格。由于不同查询的 B[j] 可能不是递增的，可以先把查询下标按照 B[j] 从小到大排序。

按这个顺序处理查询时，只需要维护一个已经进入仓库货物价格的有序数组。每次把货物补充到当前查询需要的数量，再直接取有序数组中的第 j 个位置即可。

算法步骤

1. 构造查询下标数组 order = [0, 1, ..., m-1]。
2. 按照 B[index] 从小到大排序 order。
3. 用有序数组 sortedPrices 保存已经进入仓库的货物价格。
4. 用指针 loaded 表示已经加入了前多少件货物。
5. 依次处理排序后的查询下标 idx：
   • 当 loaded < B[idx] 时，把 A[loaded] 插入有序数组。
   • 第 idx + 1 小的价格在 0 下标数组中是 sortedPrices[idx]。
   • 把结果写回 ans[idx]，保持原查询顺序。
6. 按样例格式输出数组。

复杂度分析

设货物数量为 n，查询次数为 m。

• 排序查询下标复杂度为 O(m log m)。
• 每个货物最多插入有序数组一次，数组插入最坏需要移动元素，复杂度为 O(n^2)。
• 总时间复杂度为 O(m log m + n^2)。
• 有序数组、查询顺序和答案数组占用空间，空间复杂度为 `O(n +