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::vectorstd::pairint, 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::vectorHotel hotels; std::vectorHotel 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::sortC20代码更函数式但机试环境可能不支持最新标准。#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. 测试用例与调试技巧一道题目的ACAccepted离不开充分的测试。以下是一些有价值的测试用例用例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价格310300不符合条件不参与排序。所以输出是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一家。m5但候选只有1家所以只输出一家酒店的价格80。用例4所有酒店都超标输入 50 3 2 60 10 70 20 80 30 输出 空行解析没有酒店价格50候选列表为空输出空行。调试技巧打印中间变量在筛选后、排序后分别打印candidateHotels的内容确认数据是否正确。单元测试思维将核心的排序比较函数hotelCompare单独提取出来用几组数据手动验证其返回值是否符合预期。使用边界值测试m0,n0,k0等极端情况如果题目允许。虽然实际题目会避免但自己思考能加深理解。对比输出对于复杂用例可以手动模拟排序过程与程序输出对比。6. 从这道题延伸的算法与面试思考“预定酒店”题虽然归类为“简单”或“中等”但它像一颗棱镜折射出多个重要的编程和算法知识点自定义排序是基础能力这是数据处理中最常见的操作之一。无论是前端按多列排序表格还是后端对查询结果进行复杂排序其本质都与本题相同。必须熟练掌握如何为sort、sortedPython、Arrays.sortJava等函数编写正确的比较器。问题分解能力面对一个需求能否清晰地将其分解为“筛选 - 计算关键指标 - 多级排序 - 选取Top-K - 格式化输出”这样的步骤是软件工程师的核心能力。这道题就是一个完美的微型练习。对STL/标准库的熟练度在C中能否熟练运用vector、pair/struct、sort和lambda直接决定了代码的编写效率和可读性。这体现了你的语言功底。边界条件与鲁棒性处理“不足m家”、“空列表”、“数值溢出”等情况是写出健壮代码的关键。在面试中面试官往往会追问这些边界情况。性能与清晰的权衡如前所述使用排序O(n log n)而非堆O(n log m)是基于实现复杂度和问题规模的合理权衡。在面试中能够分析这种权衡并做出合理选择比盲目追求最优复杂度更有价值。在准备华为OD或其他公司机试、面试时建议不要满足于AC本题。可以尝试以下变种练习变种1如果要求选择价格“最便宜”的m家酒店同价按距离选怎么做更简单了主键直接是price变种2如果报销额度是范围例如[k_min, k_max]又该如何筛选变种3如果输出要求不是价格而是酒店的原始索引编号如何在排序过程中保留索引信息把这些都搞明白你对排序和筛选类问题的理解会上一个大台阶。最后代码的整洁度、变量名的意义、注释的清晰度在机试的评分标准中也占有一定分量尤其是在华为这类注重工程规范的公司。养成好习惯从每一道这样的基础题开始。