资讯 / 正文

2026华为OD机考真题|货运装载顺序校验(2026.10.21)递归和分治解析与多语言代码

2026华为OD机考真题|货运装载顺序校验(2026.10.21)递归和分治解析与多语言代码

一句话结论:《货运装载顺序校验》(题号 OD_1232)是 2026.10.21 考期华为 OD 机考 200分 真题,考查 递归和分治,采用 Core 核心代码模式(无需手写输入输出)。时间复杂度 O(n log n),空间复杂度 O(n),建议写完代码后在专业 OJ 上跑满 20 组测试点再过下一题。

一、真题档案与练习入口

维度
详情
题号 / 题名OD_1232
 货运装载顺序校验
考期 / 分值
2026.10.21 / 200分
所属考点
递归和分治
做题模式
Core 核心代码模式(无需手写输入输出)
关联力扣 Hot100
排序链表
站内同类题推荐
获取利润第K大的值 / 分组字符串排序
在线免费评测
CodeSeeking 在线判题入口(20 组测试点)

二、题目描述

某物流分拣中心每天接收大量货运订单,每条订单带有一个「优先级」编号(编号越小,优先级越高,越应优先装载)。订单按到达系统的时间先后排成队列,因上游调度延迟,到达顺序与优先级顺序经常不一致。

分拣中心定义了一种「装载逆序」:对于队列中到达在前的订单  与到达在后的订单 (即 ),若订单  的优先级编号严格大于订单 ,则这两个订单构成一个装载逆序。

现给定装载优先级数组 priorities,其中 priorities[i] 表示第  个到达的订单的优先级编号,请返回装载逆序的总数。数组元素可能重复,重复值之间不构成逆序。

输入说明

输入为一个整数数组 priorities,长度 n 满足 1 ≤ n ≤ 50000,元素满足 0 ≤ priorities[i] ≤ 10^5。

输出说明

输出一个整数,表示装载逆序的总数。

示例

示例 1

输入:

[5,3,2,4,1]

输出:

8

示例 2

输入:

[1,2,3,4,5]

输出:

0

示例 3

输入:

[3,1,2]

输出:

2

三、解题思路

第一步:题目在问什么

数一数有多少对 (i, j) 满足 i < j 并且 priorities[i] > priorities[j],相等的不算。这样的一对叫逆序对。

第二步:最直接的做法为什么慢

两层循环枚举所有 (i, j),n = 50000 时约 1.25×10⁹ 对,会超时。

第三步:归并排序是什么

归并排序是一种“分而治之”的排序:

  1. 把数组从中间分成左右两半;
  2. 分别把左半、右半排好序(递归,用同样的方法);
  3. 把两个排好序的数组合并成一个:两边各有一个指针,每次比较两个指针指的数,把小的放进结果、指针后移,直到两边都放完。

第四步:合并时顺便数逆序对

所有逆序对分三类:两个数都在左半、都在右半、一个在左一个在右。前两类在递归排左右两半时已经数过了,合并时只要数第三类。

合并时,左半和右半都已经排好序。当右半当前的数 R[j] 比左半当前的数 L[i] 小、要先放 R[j] 时:左半从 L[i] 到末尾的数都 ≥ L[i] > R[j],而且它们在原数组里都在 R[j] 前面,所以一下子就找到了 mid − i + 1 个逆序对(mid 是左半最后一个位置)。

相等时先放左边的数(比较用 ≤),这样相等的两个数不会被算成逆序对。

这样每次合并是 O(长度),一共分 log n 层,总时间 O(n log n)。

用样例 1 走一遍

priorities = [5, 3, 2, 4, 1],从最小的合并开始:

合并
结果
新增逆序对
原因
[5] 和 [3]
[3, 5]
1
3 比 5 小
[3, 5] 和 [2]
[2, 3, 5]
2
2 比 3、5 都小
[4] 和 [1]
[1, 4]
1
1 比 4 小
[2, 3, 5] 和 [1, 4]
[1, 2, 3, 4, 5]
3 + 1 = 4
1 比 2、3、5 都小(+3);4 比剩下的 5 小(+1)

合计 1 + 2 + 1 + 4 = 8。

四、高频 WA 易错点(边界排查)

  • 相等的数不是逆序对:合并时比较要用 ≤,相等先放左边。
  • 新增的个数是“左半剩下的个数” mid − i + 1,不是 1。
  • 答案最大约 1.25×10⁹,接近 int 上限,累加建议用 long / long long。
  • 单个元素的数组答案是 0。

五、时间与空间复杂度

时间复杂度:O(n log n),分 log n 层,每层合并总共 O(n)。 空间复杂度:O(n),合并用的临时数组;递归深度 O(log n)。

六、参考代码实现

提示:本题属于近 8 周内最新考期真题,本文提供 Python 核心实现思路。在 CodeSeeking(https://www.codeseeking.com/problem/OD_1232)上可免费提交评测全部 20 组测试点并每日免费使用 3 次 AI 错题定位;Java / C++ / Python / JavaScript 全套四语言题解与失败用例输入/期望输出对拍可在站点内查看。

Python 实现

class Solution:    def reversePairs(self, priorities):        # 归并排序统计逆序对        arr = list(priorities)        n = len(arr)        temp = [0] * n        def merge_count(left, right):            if left >= right:                return 0            mid = (left + right) // 2            count = merge_count(left, mid) + merge_count(mid + 1, right)            i, j, k = left, mid + 1, left            while i <= mid and j <= right:                if arr[i] <= arr[j]:                    temp[k] = arr[i]                    i += 1                else:                    temp[k] = arr[j]                    j += 1                    count += mid - i + 1                k += 1            while i <= mid:                temp[k] = arr[i]                i += 1                k += 1            while j <= right:                temp[k] = arr[j]                j += 1                k += 1            for p in range(left, right + 1):                arr[p] = temp[p]            return count        return merge_count(0, n - 1)

七、在线全量自测与同类题连刷建议

  1. 全量测试点验证
    :仅通过题面 2~3 个样例往往不够,建议把代码提交到 CodeSeeking(https://www.codeseeking.com/problem/OD_1232) 跑满全部 20 组严苛测试点(支持 Java / C++ / Python / JavaScript,提交评测完全免费)。
  2. 同类题连续巩固
    :做完本题后,推荐顺手刷完对应同类题(获取利润第K大的值 / 分组字符串排序)及力扣 Hot100 原题(排序链表),彻底吃透「递归和分治」考点的常见变形。
  3. 完整 180 题刷题导航
    :2026 华为 OD 新题库 21 个考点的全部 180 题路线图与 Excel 表已开源整理在 GitHub:hwod-2026-guide。

八、常见问题(FAQ)

Q1:《货运装载顺序校验》在华为 OD 机考里属于什么难度和题型?

该题在 2026.10.21 考期分值为 200分,核心考点为 递归和分治,判题模式为 Core 核心代码模式(无需手写输入输出)。

Q2:本地样例通过但 OJ 提交报 WA(答案错误)怎么快速定位?

优先对照本文第四节的高频易错点检查边界条件;如果仍未找出问题,可在 CodeSeeking(codeseeking.com)使用普通账号每日免费 3 次的 AI 错题三段式分析 定位报错代码行,或通过失败测试点输入/期望输出对拍排查。

Q3:CodeSeeking 上刷这道题需要收费吗?

全站所有题目提交评测(含 20 组测试点)完全免费;考期 8 周之前的真题与老题题解同样免费开放,仅近 8 周最新考期四语言题解、不限次 AI 分析及失败测试点详细对拍为永久 VIP 权益。

← 返回资讯列表