华为OD机试真题解析：自定义多级排序在“预定酒店”问题中的应用

2026/7/28 5:21:10

1. 项目概述：从一道华为OD机试真题说起

最近在技术社区和求职圈里，“华为OD”这个词的热度一直居高不下，尤其是其机试环节，成了很多开发者检验算法能力和代码基本功的试金石。今天要聊的，就是一道来自华为OD C卷、分值100分的真题——“预定酒店”。这道题本身并不复杂，但它非常典型，完美地融合了排序、贪心算法和边界条件处理，是检验一个程序员基础是否扎实的绝佳案例。很多朋友在初次接触时，可能会觉得“不就是排序后取前几个吗？”，但实际动手实现，尤其是在机试那种紧张、限时的环境下，各种细节问题就会暴露无遗，比如排序规则的定义、同分（同价）情况的处理、代码的简洁与效率等。

这道题的核心场景非常生活化：小明要出差，公司给出了报销额度，他需要在指定的酒店列表中，选择价格最接近报销额度的几家酒店入住。如果有价格相同的，则优先选择距离公司更近的。这本质上是一个Top-K问题的变种，但排序的“键”是自定义的。对于C/C++开发者而言，它考察的是对std::sort自定义比较函数、容器（如vector）的使用，以及清晰的问题拆解能力。接下来，我将结合自己多年刷题和带新人的经验，不仅给出代码实现，更会深入拆解背后的思路、常见的“坑点”，以及如何写出既符合机试要求又具备工业级代码风格的解决方案。

2. 问题核心与思路拆解

2.1 题意理解与需求分析

首先，我们必须把模糊的自然语言描述转化为精确的技术需求。题目通常是这样描述的：

小明要出差，公司的报销额度是k元。现在有n家酒店可供选择，每家酒店有两个属性：价格price和距离distance（通常距离可以理解为与公司的距离，数值越小越好）。小明希望选择m家酒店入住。选择规则是：
优先选择价格低于或等于报销额度k的酒店。
在所有可选的酒店中，选择价格最接近k的m家（即价格差的绝对值最小）。
如果存在多家酒店价格差的绝对值相同，则优先选择距离更近的酒店。
如果符合条件的酒店数量不足m家，则全部选择。

输入格式通常为：

第一行：k（报销额度）,n（酒店总数）,m（需要选择的酒店数）
接下来n行：每行两个整数，分别代表酒店的price和distance。

输出格式：输出选中的m家酒店的价格列表，按选择顺序（即排序后的顺序）输出。

关键点解析：

筛选阶段：并非所有酒店都参与排序。第一步是筛选出price <= k的酒店。这是一个常见的预处理步骤，可以减少后续排序的数据量。
排序键定义：这是本题的核心。我们需要根据规则定义一个复杂的排序比较规则。主键是“价格与额度之差的绝对值”，即abs(price - k)，要求升序排列（差值越小越靠前）。次键是distance，同样要求升序排列（距离越近越靠前）。当主键相等时，次键生效。
输出控制：最终只需要输出前min(m, 筛选后酒店数量)家酒店的价格。注意边界情况，可能选不够m家。

2.2 算法与数据结构选型

这是一个典型的自定义多级排序问题，非常适合使用标准库提供的排序算法。

数据结构：使用std::vector<std::pair<int, int>>或定义一个简单的Hotel结构体来存储酒店信息。结构体的方式在可读性上更优。
算法核心：std::sort。我们需要为其提供一个自定义的比较函数或函数对象（仿函数）。
时间复杂度：筛选操作 O(n)，排序操作 O(n log n)，整体复杂度 O(n log n)，对于机试的数据范围（n 通常在 10^5 以内）完全足够。
空间复杂度：O(n)，用于存储酒店列表。

注意：有些同学可能会想到使用优先队列（堆）来维护一个大小为m的 Top-K 序列，从而将时间复杂度优化到 O(n log m)。这在理论上是更优的，但对于本题，m和n通常处于同一数量级，且实现复杂度更高，在机试的有限时间内，使用排序是更稳妥、代码更清晰的选择。机试中，“正确”和“清晰”往往比“极致优化”更重要。

3. 核心代码实现与逐行解析

这里我将分别给出 C 和 C++ 两种风格的实现，并重点讲解 C++ 的实现，因为它更充分地利用了 STL，代码更简洁优雅。

3.1 C++ 实现（推荐）

#include <iostream> #include <vector> #include <algorithm> #include <cmath> // for abs struct Hotel { int price; int distance; }; int main() { int k, n, m; std::cin >> k >> n >> m; std::vector<Hotel> hotels; std::vector<Hotel> candidateHotels; // 存储符合条件的酒店 // 1. 读取数据并初步筛选 for (int i = 0; i < n; ++i) { Hotel h; std::cin >> h.price >> h.distance; hotels.push_back(h); // 只保留价格不超过报销额度的酒店 if (h.price <= k) { candidateHotels.push_back(h); } } // 2. 定义排序规则：自定义比较函数（Lambda表达式） auto hotelCompare = [k](const Hotel& a, const Hotel& b) -> bool { int diffA = std::abs(a.price - k); int diffB = std::abs(b.price - k); // 主键：价格差绝对值，越小越靠前 if (diffA != diffB) { return diffA < diffB; } // 主键相同时，次键：距离，越小越靠前 return a.distance < b.distance; }; // 3. 对候选酒店进行排序 std::sort(candidateHotels.begin(), candidateHotels.end(), hotelCompare); // 4. 输出结果 int outputCount = std::min(m, (int)candidateHotels.size()); for (int i = 0; i < outputCount; ++i) { std::cout << candidateHotels[i].price; if (i != outputCount - 1) { std::cout << " "; } } // 如果一家符合条件的都没有，理论上应该输出空行或不输出，题目通常会有明确要求。 // 这里默认输出已选中的价格，若outputCount为0，则循环不执行，相当于输出空行。 std::cout << std::endl; return 0; }

代码逐段解析与心得：

结构体定义：使用struct Hotel比pair更清晰，成员变量名price和distance自带注释，提高了代码的可读性和可维护性。这是工业级代码的好习惯。
双容器策略：代码中使用了hotels和candidateHotels两个容器。hotels存储所有输入，candidateHotels只存符合条件的。这里有一个可优化的点：其实可以只用一个candidateHotels，在读取时直接判断if (h.price <= k)，符合条件的才存入，不符合的直接丢弃。这样更节省内存。我之所以保留两个，是为了在调试时能看到全部输入数据，方便排查问题。在实际机试或生产环境中，推荐单容器方案。
Lambda比较函数：这是现代 C++ 的优雅写法。[k]是捕获列表，表示 Lambda 函数内部可以使用外部变量k的值。比较函数的返回值是bool类型，它定义了严格的弱序关系。关键逻辑：先比较主键abs(price - k)，如果不相等，按升序返回；如果相等，再比较次键distance。这个逻辑必须与题目要求严格对应。
std::sort的应用：直接调用std::sort，传入容器的起止迭代器和比较函数。STL 的排序算法效率很高，无需自己实现。
输出控制：std::min(m, (int)candidateHotels.size())是处理边界情况的经典写法。确保不会访问candidateHotels越界。输出格式要求空格分隔，最后一个数后面无空格，这是一个常见的考点，用if (i != outputCount - 1)来判断并处理。

3.2 C 语言实现

对于坚持使用纯 C 的开发者，实现会稍显繁琐，但核心逻辑一致。

#include <stdio.h> #include <stdlib.h> // for qsort, abs typedef struct { int price; int distance; } Hotel; int k_global; // 全局变量，用于比较函数访问报销额度 // 用于qsort的比较函数 int compareHotels(const void* a, const void* b) { const Hotel* hotelA = (const Hotel*)a; const Hotel* hotelB = (const Hotel*)b; int diffA = abs(hotelA->price - k_global); int diffB = abs(hotelB->price - k_global); if (diffA != diffB) { return diffA - diffB; // 升序：如果 diffA < diffB，返回负数 } // 价格差相同，比较距离 return hotelA->distance - hotelB->distance; } int main() { int k, n, m; scanf("%d %d %d", &k, &n, &m); k_global = k; // 赋值给全局变量 Hotel* hotels = (Hotel*)malloc(n * sizeof(Hotel)); Hotel* candidateHotels = (Hotel*)malloc(n * sizeof(Hotel)); // 最多n家 int candidateCount = 0; // 读取并筛选 for (int i = 0; i < n; ++i) { scanf("%d %d", &hotels[i].price, &hotels[i].distance); if (hotels[i].price <= k) { candidateHotels[candidateCount] = hotels[i]; candidateCount++; } } // 排序 qsort(candidateHotels, candidateCount, sizeof(Hotel), compareHotels); // 输出 int outputCount = (m < candidateCount) ? m : candidateCount; for (int i = 0; i < outputCount; ++i) { printf("%d", candidateHotels[i].price); if (i != outputCount - 1) { printf(" "); } } printf("\n"); free(hotels); free(candidateHotels); return 0; }

C实现注意事项：

全局变量：因为qsort的比较函数compareHotels只能接收两个const void*参数，无法直接传入额度k，所以需要用一个全局变量k_global来传递。这是 C 语言实现此类需求时的一个常见技巧，但需注意线程安全问题（本题单线程无碍）。
内存管理：需要手动malloc和free。务必确保分配的空间足够，并在程序结束前释放，避免内存泄漏。
比较函数返回值：qsort要求比较函数返回负数、零、正数来表示小于、等于、大于的关系。return diffA - diffB;是简洁的写法。
abs函数：C 语言中abs在stdlib.h中，用于整数绝对值。

4. 关键细节、陷阱与深度优化

4.1 排序规则中的“坑”

这是最容易出错的地方。看下面这个错误的比较函数：

// 错误示例！ bool wrongCompare(const Hotel& a, const Hotel& b) { if (abs(a.price - k) < abs(b.price - k)) return true; if (a.distance < b.distance) return true; // 错误！ return false; }

这个函数错在哪里？它没有处理“当价格差相等时，才比较距离”的逻辑。如果a的价格差大于b，但a的距离小于b，这个函数会错误地返回true。正确的逻辑必须是先判断主键是否相等，不相等则按主键排序，相等才轮到次键。这就是为什么在正确代码中，我们使用if (diffA != diffB) { return diffA < diffB; }的原因。

4.2 边界条件与鲁棒性

无符合条件的酒店：即candidateHotels为空。我们的代码中outputCount = min(m, 0) = 0，循环不会执行，输出一个空行（或换行符）。这需要确认题目要求，有时要求输出空行，有时要求输出0。务必仔细审题。
m大于候选酒店数量：代码中已用std::min处理，只输出实际存在的酒店价格。
输入数据范围：题目虽未明说，但应假设价格、距离、额度均为正整数。abs(price - k)可能超出int范围吗？通常不会，但若price和k接近int边界，差值绝对值可能溢出。更稳妥的做法是使用long long存储差值，或在比较前进行转换。不过，在华为OD机试的常规数据范围内，int足矣。
距离相等时怎么办？题目只规定了价格差相同时比距离。如果距离也相同呢？题目通常默认按输入顺序或任意顺序均可。我们的比较函数在两者都相等时返回false（对于a和b相同的情况，std::sort要求比较函数返回false），这是符合要求的。如果想进一步稳定排序（即保持原始相对顺序），可以使用std::stable_sort，但本题无此必要。

4.3 性能与代码风格优化

避免冗余计算：在排序的比较函数中，我们反复计算abs(a.price - k)。对于大规模数据，可以在预处理阶段为每个候选酒店计算好这个“差值”并存储，排序时直接比较，用空间换时间。
```
struct CandidateHotel { int price; int distance; int diff; // 预计算好的 abs(price - k) }; // 排序时直接比较 diff 和 distance
```
使用reserve优化：在 C++ 中，如果对candidateHotels的大小有预估，可以先reserve(n)，避免push_back时多次重新分配内存。

更现代的 C++ 写法：可以使用std::views::filter和std::ranges::sort（C++20），代码更函数式，但机试环境可能不支持最新标准。

#include <ranges> auto candidates = hotels | std::views::filter([k](const Hotel& h){ return h.price <= k; }); // 注意：ranges需要转换为容器或直接操作，此处略复杂。

输入/输出加速：在 C++ 中，如果数据量极大（如10^6级别），可以关闭流同步来加速。
```
std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
```

5. 测试用例与调试技巧

一道题目的AC（Accepted）离不开充分的测试。以下是一些有价值的测试用例：

用例1：基础功能

输入： 300 5 3 200 500 350 1000 280 300 310 200 250 150 输出： 280 310 250

解析：额度300。价格<=300的有200,280,250。计算差值：200(100), 280(20), 250(50)。排序后：280(20), 250(50), 200(100)。输出前3个：280 250 200？等等，这里有个陷阱！酒店310价格310>300，不符合条件，不参与排序。所以输出是280 250 200。但注意，题目要求“最接近”，310的差值是10，比250的50更接近，但它超标了，所以不选。这测试了筛选逻辑。

用例2：同价差，按距离排序

输入： 200 4 2 210 50 190 100 210 30 190 80 输出： 210 190

解析：额度200。候选酒店：210(差10), 190(差10), 210(差10), 190(差10)。价格差相同，比较距离。两个210的距离是50和30，选30的那个；两个190的距离是100和80，选80的那个。最终按差值（同）和距离排序后，前两名是(210,30)和(190,80)。输出价格：210 190。

用例3：候选酒店不足m家

输入： 100 3 5 150 10 120 20 80 30 输出： 80

解析：额度100。价格<=100的只有80一家。m=5，但候选只有1家，所以只输出一家酒店的价格：80。

用例4：所有酒店都超标

输入： 50 3 2 60 10 70 20 80 30 输出： （空行）

解析：没有酒店价格<=50，候选列表为空，输出空行。

调试技巧：

打印中间变量：在筛选后、排序后，分别打印candidateHotels的内容，确认数据是否正确。
单元测试思维：将核心的排序比较函数hotelCompare单独提取出来，用几组数据手动验证其返回值是否符合预期。
使用边界值：测试m=0,n=0,k=0等极端情况（如果题目允许）。虽然实际题目会避免，但自己思考能加深理解。
对比输出：对于复杂用例，可以手动模拟排序过程，与程序输出对比。

6. 从这道题延伸的算法与面试思考

“预定酒店”题虽然归类为“简单”或“中等”，但它像一颗棱镜，折射出多个重要的编程和算法知识点：

自定义排序是基础能力：这是数据处理中最常见的操作之一。无论是前端按多列排序表格，还是后端对查询结果进行复杂排序，其本质都与本题相同。必须熟练掌握如何为sort、sorted（Python）、Arrays.sort（Java）等函数编写正确的比较器。
问题分解能力：面对一个需求，能否清晰地将其分解为“筛选 -> 计算关键指标 -> 多级排序 -> 选取Top-K -> 格式化输出”这样的步骤，是软件工程师的核心能力。这道题就是一个完美的微型练习。
对STL/标准库的熟练度：在C++中，能否熟练运用vector、pair/struct、sort和lambda，直接决定了代码的编写效率和可读性。这体现了你的语言功底。
边界条件与鲁棒性：处理“不足m家”、“空列表”、“数值溢出”等情况，是写出健壮代码的关键。在面试中，面试官往往会追问这些边界情况。
性能与清晰的权衡：如前所述，使用排序（O(n log n)）而非堆（O(n log m)）是基于实现复杂度和问题规模的合理权衡。在面试中，能够分析这种权衡并做出合理选择，比盲目追求最优复杂度更有价值。