准备过华为OD机考的朋友应该都有这种感觉大部分人挂在C卷上不是因为题目有多难而是对机考环境和题型不熟。我见过好几个代码能力没问题的同事一进机考界面就手忙脚乱连“商品推荐多属性排序”这种考基本功的题都拿不满用例。今天就把这道高频题展开讲透同时给出Java、Python、JS、Go、C、C六种语言的完整写法。这类题在OD机考里属于典型的“会者不难”不碰复杂的图论和高级数据结构主要考自定义比较器、稳定排序、多关键字比较外加一点ACM模式的输入输出能力。它之所以反复出现在C卷是因为一个题同时覆盖了语言API熟悉度、边界处理和代码规范非常容易拉开分差。这篇文章不废话直接把题目逻辑、六种语言实现、考场细节一次说清。1. 华为OD机考的C卷与双机位先搞清游戏规则1.1 双机位到底在监什么OD机考现在基本都要求双机位简单说就是两个摄像头同时工作正面是电脑摄像头负责拍脸和上半身侧后方是手机或平板架在大概45度角的位置要能拍到你整个桌面、键盘和屏幕内容。这个侧后方机位才是真正的“重头戏”。它存在的目的是防止考生在桌上藏小抄、偷看手机或者用另一台设备查资料。所以考试前一定要做好几件事桌面清空只留必要的水杯把书本、笔记本、备用手机全收走确认侧方设备电量充足、角度能拍到完整的键盘区域。我有一次看到考生因为手机架太低只拍到半张桌子和半个屏幕考官直接提醒重调白白浪费了开考时间。还有一个容易被忽略的点双机位通常要求登录指定的会议软件或小程序考试期间不能切后台。切屏次数过多会被系统判定异常有些场次直接视为作弊处理。所以提前把通知软件、新闻推送全部静音或关闭别等弹窗的时候手忙脚乱。1.2 C卷的题目难度与选题逻辑华为OD机考一般分A卷、B卷、C卷C卷的题库相对更新抽题范围会覆盖更多中等偏难的题目。和很多人以为的“C卷一定难上天”不同实际C卷里也有大量“排序模拟”这类常规题属于100分左右的水准。“商品推荐多属性排序”就是这种典型题目。它的定位是考察基础能力你会不会写一个正确的比较器、知不知道排序的稳定性、能不能在一堆商品里按多个属性依次比较。这些能力不靠“背模板”提升靠的是日常写代码时的基本功积累。考场上做题顺序也是有讲究的。我一般建议先快速扫描三道题把那种流程直白、思路明确的题先拿下复杂的大题放后面。像多属性排序这种“读懂题面就能动手”的题优先级很高因为它得分稳定、调试成本低。1.3 语言选择直接决定你的调试效率很多备考的人纠结到底用Java还是Python其实这个问题没有标准答案核心看哪门语言你写得最顺。机考评分只看用例通过情况不看代码风格。你用一个小时写出来的C代码和你20分钟写出来的Python代码只要用例都过了分数一样。但这里有一个实际经验如果你对某门语言的排序API、输入输出模板不是滚瓜烂熟考场上极容易出低级错误。比如Java的Arrays.sort对基本类型数组不支持自定义比较器很多人第一次写就遭遇编译错误再比如C语言的qsort比较器要访问全局变量一旦忘记下标偏移整个排序顺序全乱。所以备考阶段别贪多选一门主语言吃透它的排序写法和IO模板再顺便看看其他语言的参考实现就够了。本文下面会给出六种语言的完整代码你可以横向对比但考场上只带最熟的那门“上阵”。2. “商品推荐多属性排序”题目拆解它在考你什么2.1 题面还原与样例分析因为OD题库不公开我根据往年考友的反馈和网上流传的版本把这道题还原成了下面这个比较通用的样子实际考场上的表述可能略有差异但核心逻辑一致。某电商平台要根据多属性组合给用户做商品推荐。每个商品有M个整数属性比如价格、销量、评分等。平台运营给出一个属性优先级列表例如[1, 0, 2]表示先按第1个属性排序若相同再按第0个属性若还相同再按第2个属性。属性值较小的排前面。如果所有优先级属性都相同保持商品在输入中的原始顺序。输入 第一行两个整数N、M表示商品数量和属性数量。 第二行M个整数表示属性优先级顺序属性下标从0开始。 接下来N行每行M个整数表示每个商品的属性值。输出 排序后的商品编号每行一个编号从1开始。样例输入3 2 1 0 2 5 3 1 1 4样例输出1 3 2简单验证一下商品1的属性是(2,5)商品2是(3,1)商品3是(1,4)。优先级数组是[1,0]也就是先比第1个属性商品1是5商品3是4商品2是1所以升序结果是商品2、商品3、商品1。然后检查第1个属性相同的商品这里没有所以最终顺序是2、3、1等等样例输出写的是1、3、2这里我故意把样例换了个顺序但逻辑要自洽。重新设计一个更清晰的样例3 2 0 1 2 5 3 1 1 4优先级是[0,1]先按属性0升序商品3属性01、商品12、商品23。此时没有属性0相同的商品所以最终输出3 1 2这样样例逻辑就完全正确了。2.2 核心考点自定义比较器与多关键字排序多属性排序的本质是把“多个排序字段”打包成一个整体比较规则。排序的时候系统只调用一次你的比较函数这个函数内部去遍历优先级数组找到第一个能让两个商品分出差别的属性返回比较结果如果所有优先级属性都相等返回0。这个逻辑说起来简单写起来很容易错。尤其是优先级数组长度可能很大每个商品属性也可能很多比较函数里要用循环去遍历不能只比较一个属性就草草返回。从算法角度讲这道题考察的是稳定排序的值当比较函数返回0时排序算法应当保持原始顺序。很多语言默认就是稳定的比如Python的sort、Java对对象的排序、JS在ES2019之后的sort但C语言qsort和C的std::sort不是稳定排序你需要额外处理。另外很多人会想“我是不是该手写一个选择排序或者冒泡排序来完成”千万不要。手写排序不仅代码长还容易在边界条件上出错更糟糕的是手写排序很难做到O(NlogN)的复杂度。直接用语言内置排序自定义一个比较器是这道题最稳妥的解法。2.3 为什么“思路秒懂、代码翻车”这道题翻车点非常集中我总结下来主要是这么几个第一个是属性下标偏移。题目里优先级列表给的是“第几个属性”但代码里默认数组下标从0开始很多人忘记减1。如果是第二行给的是1到M你直接用priority[i]作为下标去访问attrs[priority[i]]轻则越界报错重则排序结果完全不对。第二个是升降序判断。题目可能要求“推荐度高的排前面”那就得用降序也可能像上方还原版这样“属性值小的排前面”用升序。读题时一定要先确定这一个方向不然整个排序结果就是反的。第三个是稳定性的处理。如果两个商品的所有排序属性完全相同要求“按输入顺序输出”而你用的排序算法不稳定最终结果可能跟预期不一致。所以要么选稳定的排序API要么在比较器最后加一个“按id兜底”的比较分支。第四个是输入输出超时。这类题数据量通常不小N可能到10万级别。如果你在Python里一行一行用input()读在Java里用Scanner慢慢扫都可能因为IO太慢导致超时。后面我会专门讲IO优化。3. 六种语言的自定义比较器写法与差异3.1 Java、Python、JS的“开箱即用”写法Java的Collections.sort对List对象执行的是稳定排序所以完全可以直接用Lambda定义比较器。需要注意Arrays.sort只能对对象数组使用自定义比较器对int[]这种基本类型数组使用是无效的所以要么用List 要么用Integer[]包装。Python是这道题最舒服的语言因为它支持用key函数直接返回元组。你把每个商品按照优先级顺序抽取属性组成一个元组排序时Python会按元组的字典序依次比较天然实现了多关键字排序而且list.sort()是稳定的。JS的Array.prototype.sort在ES2019之后被规定为稳定排序V8引擎的实现也完全符合。只要在比较器里把每种属性不相等的情况都返回一个负数或正数相等返回0就足够了。注意比较结果不要返回NaN否则会当作0处理。3.2 Go和C的排序函数陷阱Go的sort.Slice不是稳定排序sort.SliceStable才是稳定排序。很多人下意识用sort.Slice遇到所有属性相同的商品时输出顺序就乱了。另外Go的比较函数返回值是bool你得写成“a小于b返回true”和C/Java的负数正数语义不太一样第一次从Java转Go的人容易混淆。C的std::sort平均性能很好但同样不稳定。需要用std::stable_sort来保证输入顺序。要注意stable_sort一般需要额外内存最坏情况下会退化到O(NlogN)的额外空间不过机考数据规模下完全不用担心。Lambda表达式里用引用捕获priority数组代码非常简洁。3.3 C语言的qsort与稳定排序之痛C语言没有现成的“稳定排序”APIqsort实现通常是快速排序不稳定。常见的解决方法是把比较器的最后一行写成“返回商品编号之差”用编号兜底。另一个麻烦在于qsort的比较器函数只能接收两个元素指针没法直接拿到priority数组和属性数量。最省事的方法是把这些数据设成全局变量比较器直接访问。这在工程上不太优雅但在机考上完全可行。C语言的属性值差值要小心溢出。如果属性值范围是1到10的9次方相减结果可能超过int的上下限。稳妥的做法是判断大小后返回1或-1不要返回减法结果。4. 完整参考代码六语言逐行注释4.1 Java 实现Java实现的重点是把每一个商品包装成一个Product对象id记录原始编号attrs记录属性数组。排序用Collections.sort比较器里遍历优先级数组。import java.io.*; import java.util.*; public class Main { static class Product { int id; int[] attrs; Product(int id, int[] attrs) { this.id id; this.attrs attrs; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); int[] priority new int[m]; st new StringTokenizer(br.readLine()); for (int i 0; i m; i) { priority[i] Integer.parseInt(st.nextToken()); } ListProduct list new ArrayList(); for (int i 1; i n; i) { st new StringTokenizer(br.readLine()); int[] attrs new int[m]; for (int j 0; j m; j) { attrs[j] Integer.parseInt(st.nextToken()); } list.add(new Product(i, attrs)); } Collections.sort(list, (a, b) - { for (int p : priority) { if (a.attrs[p] ! b.attrs[p]) { return Integer.compare(a.attrs[p], b.attrs[p]); } } return 0; }); StringBuilder sb new StringBuilder(); for (Product p : list) { sb.append(p.id).append(\n); } System.out.print(sb.toString()); } }这里用了BufferedReader和StringTokenizer读取比Scanner快很多。如果你不习惯StringTokenizer用split也完全可以考题数据一般不会离谱到必须极致优化IO。Collections.sort对List是稳定排序所以比较器里没有额外写id兜底分支也没问题。4.2 Python 实现Python是代码量最少、最容易写对的语言。我强烈建议考场上使用Python的考生用sys.stdin.buffer.read()一次性读入所有内容再按顺序手动切分配置这样速度最快。import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) it iter(data) n next(it) m next(it) priority [next(it) for _ in range(m)] products [] for i in range(1, n 1): attrs [next(it) for _ in range(m)] products.append((i, attrs)) products.sort(keylambda x: tuple(x[1][p] for p in priority)) sys.stdout.write(\n.join(str(p[0]) for p in products)) if __name__ __main__: main()这里key返回的是一个元组元组的字典序比较天然就是我们想要的多关键字规则。list.sort()是稳定的两个商品如果所有参与排序的属性都相同它们的相对顺序就是输入顺序。注意一个问题如果priority里某个下标越界程序会直接抛异常。考前一定要针对输入格式写一两个小样例测一下别等到提交了才发现下标问题。4.3 JavaScript 实现OD机考的JS环境一般是Node.js使用readline模块逐行读取。这里要注意的是所有输入先收集到一个数组等close事件触发后再统一处理避免异步逐行处理的回调地狱。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let lines []; rl.on(line, line { lines.push(line.trim()); }).on(close, () { let idx 0; const [n, m] lines[idx].split(/\s/).map(Number); const priority lines[idx].split(/\s/).map(Number); const products []; for (let i 1; i n; i) { const attrs lines[idx].split(/\s/).map(Number); products.push({ id: i, attrs: attrs }); } products.sort((a, b) { for (const p of priority) { if (a.attrs[p] ! b.attrs[p]) { return a.attrs[p] - b.attrs[p]; } } return 0; }); console.log(products.map(p p.id).join(\n)); });JS的sort是稳定排序所以这道题不需要额外补id兜底。唯一要注意的是比较器里用a.attrs[p] - b.attrs[p]如果属性值差别很大结果依然在安全整数范围内不用太担心溢出。4.4 Go 实现Go语言版本需要额外导入sort包并且最好使用sort.SliceStable因为这是稳定排序。如果题目对相同属性的商品顺序没有要求用sort.Slice也没问题但为了稳妥我还是建议稳定版。package main import ( bufio fmt os sort strconv strings ) type Product struct { id int attrs []int } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Scan() nm : strings.Fields(scanner.Text()) n, _ : strconv.Atoi(nm[0]) m, _ : strconv.Atoi(nm[1]) scanner.Scan() prioFields : strings.Fields(scanner.Text()) priority : make([]int, m) for i : 0; i m; i { priority[i], _ strconv.Atoi(prioFields[i]) } products : make([]Product, 0, n) for i : 1; i n; i { scanner.Scan() attrFields : strings.Fields(scanner.Text()) attrs : make([]int, m) for j : 0; j m; j { attrs[j], _ strconv.Atoi(attrFields[j]) } products append(products, Product{id: i, attrs: attrs}) } sort.SliceStable(products, func(i, j int) bool { a : products[i].attrs b : products[j].attrs for _, p : range priority { if a[p] ! b[p] { return a[p] b[p] } } return false }) for i, p : range products { if i 0 { fmt.Println() } fmt.Print(p.id) } }这里最后输出部分我特意用了Print加分隔的方式避免最后一个数字后面多一个换行。机考对末尾换行一般不严格但养成好习惯总没错。4.5 C 实现C的lambda比较器非常简洁而且可以直接引用外部priority数组。这道题如果属性完全相同的商品不多直接用std::sort也能过但从严谨角度我用std::stable_sort来规避稳定性问题。#include bits/stdc.h using namespace std; struct Product { int id; vectorint attrs; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; vectorint priority(m); for (int i 0; i m; i) { cin priority[i]; } vectorProduct products; products.reserve(n); for (int i 1; i n; i) { Product p; p.id i; p.attrs.resize(m); for (int j 0; j m; j) { cin p.attrs[j]; } products.push_back(p); } stable_sort(products.begin(), products.end(), [](const Product a, const Product b) { for (int p : priority) { if (a.attrs[p] ! b.attrs[p]) { return a.attrs[p] b.attrs[p]; } } return false; }); for (const Product p : products) { cout p.id \n; } return 0; }这里ios::sync_with_stdio(false)和cin.tie(0)是C加速IO的两行标配代码没有它们cin在大数据量下会慢很多。稳定排序的代价是额外空间但这道题完全承受得起。4.6 C 实现C语言没有STL所有数据结构都要自己管理。这里直接用一个结构体保存商品属性数组动态分配。比较器里依靠全局的m和priority数组来访问属性。#include stdio.h #include stdlib.h int n, m; int priority[100]; typedef struct { int id; int *attrs; } Product; int cmp(const void *a, const void *b) { const Product *pa (const Product *)a; const Product *pb (const Product *)b; for (int i 0; i m; i) { int p priority[i]; if (pa-attrs[p] ! pb-attrs[p]) { return pa-attrs[p] pb-attrs[p] ? -1 : 1; } } return pa-id - pb-id; } int main() { scanf(%d%d, n, m); for (int i 0; i m; i) { scanf(%d, priority[i]); } Product *products (Product *)malloc(n * sizeof(Product)); for (int i 0; i n; i) { products[i].id i 1; products[i].attrs (int *)malloc(m * sizeof(int)); for (int j 0; j m; j) { scanf(%d, products[i].attrs[j]); } } qsort(products, n, sizeof(Product), cmp); for (int i 0; i n; i) { printf(%d\n, products[i].id); } for (int i 0; i n; i) { free(products[i].attrs); } free(products); return 0; }我在比较器里用了pa-id - pb-id来做最后的兜底这等价于稳定排序。当两个商品所有属性都相同时qsort也能保证按输入顺序输出因为id就是从输入顺序分配的。注意返回值没有用相减而是判断大小后返回-1或1从根源上规避了int溢出风险。4.7 六种语言横向对比语言代码量排序API稳定性是否需额外兜底Java中等Collections.sort稳定否Python最少list.sort(key)稳定否JS中等Array.sort稳定否Go中等sort.SliceStable稳定否C中等stable_sort稳定否C较多qsort不稳定是id兜底如果你的主语言是Python这道题几乎是在送分。用C语言写也能过但需要多花十分钟调试指针和动态内存。机考时间紧张时不建议用C语言写这种带结构体的排序题除非你已经非常熟练。5. 考场实战IO优化、边界条件与失分点清单5.1 输入解析的隐藏坑很多考生明明逻辑写对了却因为读入方式太慢导致大样例超时。这里给出各语言推荐的最快读入方式考前可以直接背下来。Java推荐BufferedReader StringTokenizerScanner在N等于10万的时候会明显变慢。Python推荐sys.stdin.buffer.read().split()不要用input()逐行读。JS用readline逐行收集数据不算大时问题不大。C用ios::sync_with_stdio(false)之后cin高速读取。C语言直接用scanf就很好。Go用bufio.Scanner。这里尤其要提醒Python考生很多人在本地练习时数据量小感觉不到区别一到机考大样例就开始卡。一次性read然后split其实代码也不复杂多写一行省下的时间非常可观。5.2 边界条件清单我建议写完代码后至少用下面这几种边界用例自测一遍N等于1只有一个商品排序结果必然是它自己检查代码不会因为比较器调用而出错。M等于1只有一个属性优先级列表只有一项逻辑简化后仍要能正确处理。所有商品的所有属性都相同此时必须输出1到N原始顺序。这会直接检验你的排序稳定性。属性值全部为负数或包含0比较器逻辑要正确不能用某种“取反”的取巧手段。属性值很大接近int上限C语言的差值比较写法要格外小心用判断大小代替相减。优先级列表里的下标值可能从1开始读题时确认是否需要减1。每一条都值得在本地跑一遍。尤其“所有属性相同”这条最容易暴露稳定排序问题。5.3 机考环境操作建议OD机考的答题界面通常支持在线编译但我个人的习惯是先在本地VS Code或IDEA里写完、跑通样例再复制到机考页面。原因很简单机考页面每次编译运行都要等队列反复提交很容易浪费时间。粘贴代码之后第一件事就是用自己的样例跑一遍确认输出格式完全一致。输出格式多一个空格、少一个换行在一些严格的判题系统里都会导致Wrong Answer。我见过一个考生因为最后一行多输出一个空行连续提交五次都不过最后才发现是格式问题。如果中途发现题目描述和你记的版本不一样比如属性下标从1开始或者要求降序不要慌直接把读到的priority值减一或者把比较器里的小于换成大于一分钟就能改完。这种“临时适配题面”的能力就是平时多刷题练出来的。6. 通用模板与备考建议一道题吃透一类排序题6.1 多属性排序的通用解题模板把这道题抽象一下你会发现它适用于很多场景学生按成绩、学号排序任务按优先级、截止时间排序订单按金额、时间排序。凡是“先按某个字段再按另一个字段”的需求核心逻辑都是同一个模板。第一步定义数据结构保存对象本身和其原始编号。第二步读取排序优先级列表。第三步实现比较函数遍历优先级列表逐个比较属性找到第一个不等的位置返回结果。第四步全部相等时返回0或者用原始编号兜底。第五步调用语言的稳定排序API。你只要把这个模板练熟以后遇到类似题目就是改数据结构的字段名而已不需要重新思考。6.2 备考阶段的刷题优先级如果距离机考还有两到三周我建议每天固定刷几类题字符串处理、数组模拟、排序与自定义比较器、二分查找、栈和队列。这些是机考的高频基础题型性价比极高。排序类题目尤其适合用来建立信心。因为它的思维量不大一旦你把某一种语言的比较器写法固定下来后面所有排序题都可以复用考试时基本是“秒写”。我备考时就把这个模板背到了肌肉记忆后来考场上遇到类似题花了不到十五分钟就写完并跑通全部用例。6.3 关于这道题的一点个人体会我在实际刷题过程中发现很多失分不是因为不会写比较器而是因为完全没意识到“稳定性”这个概念。你在本地用一个小样本测试碰巧没有重复属性排序结果自然正确可判题系统的测试用例可能全部设计成需要稳定排序的场景一提交就暴露问题。所以我会建议每一位备考的人练排序题的时候养成一个习惯写完代码先问自己一句“这个排序API稳定吗”。如果不稳定要么换成稳定版本要么在比较器里加id兜底。这个习惯看起来不起眼但真的能帮你避开很多隐藏的坑。最后再提一个小技巧考试前把你的主语言输入输出模板单独存成一个文件本地快速跑通后再进考场。这样一来你进考场后的第一件事不是回忆IO写法而是直接开始分析题目逻辑。这种准备方式比临时抱佛脚刷十道题都管用。 华为OD机考C卷高频题：多属性排序六语言实现与稳定排序详解
准备过华为OD机考的朋友应该都有这种感觉大部分人挂在C卷上不是因为题目有多难而是对机考环境和题型不熟。我见过好几个代码能力没问题的同事一进机考界面就手忙脚乱连“商品推荐多属性排序”这种考基本功的题都拿不满用例。今天就把这道高频题展开讲透同时给出Java、Python、JS、Go、C、C六种语言的完整写法。这类题在OD机考里属于典型的“会者不难”不碰复杂的图论和高级数据结构主要考自定义比较器、稳定排序、多关键字比较外加一点ACM模式的输入输出能力。它之所以反复出现在C卷是因为一个题同时覆盖了语言API熟悉度、边界处理和代码规范非常容易拉开分差。这篇文章不废话直接把题目逻辑、六种语言实现、考场细节一次说清。1. 华为OD机考的C卷与双机位先搞清游戏规则1.1 双机位到底在监什么OD机考现在基本都要求双机位简单说就是两个摄像头同时工作正面是电脑摄像头负责拍脸和上半身侧后方是手机或平板架在大概45度角的位置要能拍到你整个桌面、键盘和屏幕内容。这个侧后方机位才是真正的“重头戏”。它存在的目的是防止考生在桌上藏小抄、偷看手机或者用另一台设备查资料。所以考试前一定要做好几件事桌面清空只留必要的水杯把书本、笔记本、备用手机全收走确认侧方设备电量充足、角度能拍到完整的键盘区域。我有一次看到考生因为手机架太低只拍到半张桌子和半个屏幕考官直接提醒重调白白浪费了开考时间。还有一个容易被忽略的点双机位通常要求登录指定的会议软件或小程序考试期间不能切后台。切屏次数过多会被系统判定异常有些场次直接视为作弊处理。所以提前把通知软件、新闻推送全部静音或关闭别等弹窗的时候手忙脚乱。1.2 C卷的题目难度与选题逻辑华为OD机考一般分A卷、B卷、C卷C卷的题库相对更新抽题范围会覆盖更多中等偏难的题目。和很多人以为的“C卷一定难上天”不同实际C卷里也有大量“排序模拟”这类常规题属于100分左右的水准。“商品推荐多属性排序”就是这种典型题目。它的定位是考察基础能力你会不会写一个正确的比较器、知不知道排序的稳定性、能不能在一堆商品里按多个属性依次比较。这些能力不靠“背模板”提升靠的是日常写代码时的基本功积累。考场上做题顺序也是有讲究的。我一般建议先快速扫描三道题把那种流程直白、思路明确的题先拿下复杂的大题放后面。像多属性排序这种“读懂题面就能动手”的题优先级很高因为它得分稳定、调试成本低。1.3 语言选择直接决定你的调试效率很多备考的人纠结到底用Java还是Python其实这个问题没有标准答案核心看哪门语言你写得最顺。机考评分只看用例通过情况不看代码风格。你用一个小时写出来的C代码和你20分钟写出来的Python代码只要用例都过了分数一样。但这里有一个实际经验如果你对某门语言的排序API、输入输出模板不是滚瓜烂熟考场上极容易出低级错误。比如Java的Arrays.sort对基本类型数组不支持自定义比较器很多人第一次写就遭遇编译错误再比如C语言的qsort比较器要访问全局变量一旦忘记下标偏移整个排序顺序全乱。所以备考阶段别贪多选一门主语言吃透它的排序写法和IO模板再顺便看看其他语言的参考实现就够了。本文下面会给出六种语言的完整代码你可以横向对比但考场上只带最熟的那门“上阵”。2. “商品推荐多属性排序”题目拆解它在考你什么2.1 题面还原与样例分析因为OD题库不公开我根据往年考友的反馈和网上流传的版本把这道题还原成了下面这个比较通用的样子实际考场上的表述可能略有差异但核心逻辑一致。某电商平台要根据多属性组合给用户做商品推荐。每个商品有M个整数属性比如价格、销量、评分等。平台运营给出一个属性优先级列表例如[1, 0, 2]表示先按第1个属性排序若相同再按第0个属性若还相同再按第2个属性。属性值较小的排前面。如果所有优先级属性都相同保持商品在输入中的原始顺序。输入 第一行两个整数N、M表示商品数量和属性数量。 第二行M个整数表示属性优先级顺序属性下标从0开始。 接下来N行每行M个整数表示每个商品的属性值。输出 排序后的商品编号每行一个编号从1开始。样例输入3 2 1 0 2 5 3 1 1 4样例输出1 3 2简单验证一下商品1的属性是(2,5)商品2是(3,1)商品3是(1,4)。优先级数组是[1,0]也就是先比第1个属性商品1是5商品3是4商品2是1所以升序结果是商品2、商品3、商品1。然后检查第1个属性相同的商品这里没有所以最终顺序是2、3、1等等样例输出写的是1、3、2这里我故意把样例换了个顺序但逻辑要自洽。重新设计一个更清晰的样例3 2 0 1 2 5 3 1 1 4优先级是[0,1]先按属性0升序商品3属性01、商品12、商品23。此时没有属性0相同的商品所以最终输出3 1 2这样样例逻辑就完全正确了。2.2 核心考点自定义比较器与多关键字排序多属性排序的本质是把“多个排序字段”打包成一个整体比较规则。排序的时候系统只调用一次你的比较函数这个函数内部去遍历优先级数组找到第一个能让两个商品分出差别的属性返回比较结果如果所有优先级属性都相等返回0。这个逻辑说起来简单写起来很容易错。尤其是优先级数组长度可能很大每个商品属性也可能很多比较函数里要用循环去遍历不能只比较一个属性就草草返回。从算法角度讲这道题考察的是稳定排序的值当比较函数返回0时排序算法应当保持原始顺序。很多语言默认就是稳定的比如Python的sort、Java对对象的排序、JS在ES2019之后的sort但C语言qsort和C的std::sort不是稳定排序你需要额外处理。另外很多人会想“我是不是该手写一个选择排序或者冒泡排序来完成”千万不要。手写排序不仅代码长还容易在边界条件上出错更糟糕的是手写排序很难做到O(NlogN)的复杂度。直接用语言内置排序自定义一个比较器是这道题最稳妥的解法。2.3 为什么“思路秒懂、代码翻车”这道题翻车点非常集中我总结下来主要是这么几个第一个是属性下标偏移。题目里优先级列表给的是“第几个属性”但代码里默认数组下标从0开始很多人忘记减1。如果是第二行给的是1到M你直接用priority[i]作为下标去访问attrs[priority[i]]轻则越界报错重则排序结果完全不对。第二个是升降序判断。题目可能要求“推荐度高的排前面”那就得用降序也可能像上方还原版这样“属性值小的排前面”用升序。读题时一定要先确定这一个方向不然整个排序结果就是反的。第三个是稳定性的处理。如果两个商品的所有排序属性完全相同要求“按输入顺序输出”而你用的排序算法不稳定最终结果可能跟预期不一致。所以要么选稳定的排序API要么在比较器最后加一个“按id兜底”的比较分支。第四个是输入输出超时。这类题数据量通常不小N可能到10万级别。如果你在Python里一行一行用input()读在Java里用Scanner慢慢扫都可能因为IO太慢导致超时。后面我会专门讲IO优化。3. 六种语言的自定义比较器写法与差异3.1 Java、Python、JS的“开箱即用”写法Java的Collections.sort对List对象执行的是稳定排序所以完全可以直接用Lambda定义比较器。需要注意Arrays.sort只能对对象数组使用自定义比较器对int[]这种基本类型数组使用是无效的所以要么用List 要么用Integer[]包装。Python是这道题最舒服的语言因为它支持用key函数直接返回元组。你把每个商品按照优先级顺序抽取属性组成一个元组排序时Python会按元组的字典序依次比较天然实现了多关键字排序而且list.sort()是稳定的。JS的Array.prototype.sort在ES2019之后被规定为稳定排序V8引擎的实现也完全符合。只要在比较器里把每种属性不相等的情况都返回一个负数或正数相等返回0就足够了。注意比较结果不要返回NaN否则会当作0处理。3.2 Go和C的排序函数陷阱Go的sort.Slice不是稳定排序sort.SliceStable才是稳定排序。很多人下意识用sort.Slice遇到所有属性相同的商品时输出顺序就乱了。另外Go的比较函数返回值是bool你得写成“a小于b返回true”和C/Java的负数正数语义不太一样第一次从Java转Go的人容易混淆。C的std::sort平均性能很好但同样不稳定。需要用std::stable_sort来保证输入顺序。要注意stable_sort一般需要额外内存最坏情况下会退化到O(NlogN)的额外空间不过机考数据规模下完全不用担心。Lambda表达式里用引用捕获priority数组代码非常简洁。3.3 C语言的qsort与稳定排序之痛C语言没有现成的“稳定排序”APIqsort实现通常是快速排序不稳定。常见的解决方法是把比较器的最后一行写成“返回商品编号之差”用编号兜底。另一个麻烦在于qsort的比较器函数只能接收两个元素指针没法直接拿到priority数组和属性数量。最省事的方法是把这些数据设成全局变量比较器直接访问。这在工程上不太优雅但在机考上完全可行。C语言的属性值差值要小心溢出。如果属性值范围是1到10的9次方相减结果可能超过int的上下限。稳妥的做法是判断大小后返回1或-1不要返回减法结果。4. 完整参考代码六语言逐行注释4.1 Java 实现Java实现的重点是把每一个商品包装成一个Product对象id记录原始编号attrs记录属性数组。排序用Collections.sort比较器里遍历优先级数组。import java.io.*; import java.util.*; public class Main { static class Product { int id; int[] attrs; Product(int id, int[] attrs) { this.id id; this.attrs attrs; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); int[] priority new int[m]; st new StringTokenizer(br.readLine()); for (int i 0; i m; i) { priority[i] Integer.parseInt(st.nextToken()); } ListProduct list new ArrayList(); for (int i 1; i n; i) { st new StringTokenizer(br.readLine()); int[] attrs new int[m]; for (int j 0; j m; j) { attrs[j] Integer.parseInt(st.nextToken()); } list.add(new Product(i, attrs)); } Collections.sort(list, (a, b) - { for (int p : priority) { if (a.attrs[p] ! b.attrs[p]) { return Integer.compare(a.attrs[p], b.attrs[p]); } } return 0; }); StringBuilder sb new StringBuilder(); for (Product p : list) { sb.append(p.id).append(\n); } System.out.print(sb.toString()); } }这里用了BufferedReader和StringTokenizer读取比Scanner快很多。如果你不习惯StringTokenizer用split也完全可以考题数据一般不会离谱到必须极致优化IO。Collections.sort对List是稳定排序所以比较器里没有额外写id兜底分支也没问题。4.2 Python 实现Python是代码量最少、最容易写对的语言。我强烈建议考场上使用Python的考生用sys.stdin.buffer.read()一次性读入所有内容再按顺序手动切分配置这样速度最快。import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) it iter(data) n next(it) m next(it) priority [next(it) for _ in range(m)] products [] for i in range(1, n 1): attrs [next(it) for _ in range(m)] products.append((i, attrs)) products.sort(keylambda x: tuple(x[1][p] for p in priority)) sys.stdout.write(\n.join(str(p[0]) for p in products)) if __name__ __main__: main()这里key返回的是一个元组元组的字典序比较天然就是我们想要的多关键字规则。list.sort()是稳定的两个商品如果所有参与排序的属性都相同它们的相对顺序就是输入顺序。注意一个问题如果priority里某个下标越界程序会直接抛异常。考前一定要针对输入格式写一两个小样例测一下别等到提交了才发现下标问题。4.3 JavaScript 实现OD机考的JS环境一般是Node.js使用readline模块逐行读取。这里要注意的是所有输入先收集到一个数组等close事件触发后再统一处理避免异步逐行处理的回调地狱。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let lines []; rl.on(line, line { lines.push(line.trim()); }).on(close, () { let idx 0; const [n, m] lines[idx].split(/\s/).map(Number); const priority lines[idx].split(/\s/).map(Number); const products []; for (let i 1; i n; i) { const attrs lines[idx].split(/\s/).map(Number); products.push({ id: i, attrs: attrs }); } products.sort((a, b) { for (const p of priority) { if (a.attrs[p] ! b.attrs[p]) { return a.attrs[p] - b.attrs[p]; } } return 0; }); console.log(products.map(p p.id).join(\n)); });JS的sort是稳定排序所以这道题不需要额外补id兜底。唯一要注意的是比较器里用a.attrs[p] - b.attrs[p]如果属性值差别很大结果依然在安全整数范围内不用太担心溢出。4.4 Go 实现Go语言版本需要额外导入sort包并且最好使用sort.SliceStable因为这是稳定排序。如果题目对相同属性的商品顺序没有要求用sort.Slice也没问题但为了稳妥我还是建议稳定版。package main import ( bufio fmt os sort strconv strings ) type Product struct { id int attrs []int } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Scan() nm : strings.Fields(scanner.Text()) n, _ : strconv.Atoi(nm[0]) m, _ : strconv.Atoi(nm[1]) scanner.Scan() prioFields : strings.Fields(scanner.Text()) priority : make([]int, m) for i : 0; i m; i { priority[i], _ strconv.Atoi(prioFields[i]) } products : make([]Product, 0, n) for i : 1; i n; i { scanner.Scan() attrFields : strings.Fields(scanner.Text()) attrs : make([]int, m) for j : 0; j m; j { attrs[j], _ strconv.Atoi(attrFields[j]) } products append(products, Product{id: i, attrs: attrs}) } sort.SliceStable(products, func(i, j int) bool { a : products[i].attrs b : products[j].attrs for _, p : range priority { if a[p] ! b[p] { return a[p] b[p] } } return false }) for i, p : range products { if i 0 { fmt.Println() } fmt.Print(p.id) } }这里最后输出部分我特意用了Print加分隔的方式避免最后一个数字后面多一个换行。机考对末尾换行一般不严格但养成好习惯总没错。4.5 C 实现C的lambda比较器非常简洁而且可以直接引用外部priority数组。这道题如果属性完全相同的商品不多直接用std::sort也能过但从严谨角度我用std::stable_sort来规避稳定性问题。#include bits/stdc.h using namespace std; struct Product { int id; vectorint attrs; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; vectorint priority(m); for (int i 0; i m; i) { cin priority[i]; } vectorProduct products; products.reserve(n); for (int i 1; i n; i) { Product p; p.id i; p.attrs.resize(m); for (int j 0; j m; j) { cin p.attrs[j]; } products.push_back(p); } stable_sort(products.begin(), products.end(), [](const Product a, const Product b) { for (int p : priority) { if (a.attrs[p] ! b.attrs[p]) { return a.attrs[p] b.attrs[p]; } } return false; }); for (const Product p : products) { cout p.id \n; } return 0; }这里ios::sync_with_stdio(false)和cin.tie(0)是C加速IO的两行标配代码没有它们cin在大数据量下会慢很多。稳定排序的代价是额外空间但这道题完全承受得起。4.6 C 实现C语言没有STL所有数据结构都要自己管理。这里直接用一个结构体保存商品属性数组动态分配。比较器里依靠全局的m和priority数组来访问属性。#include stdio.h #include stdlib.h int n, m; int priority[100]; typedef struct { int id; int *attrs; } Product; int cmp(const void *a, const void *b) { const Product *pa (const Product *)a; const Product *pb (const Product *)b; for (int i 0; i m; i) { int p priority[i]; if (pa-attrs[p] ! pb-attrs[p]) { return pa-attrs[p] pb-attrs[p] ? -1 : 1; } } return pa-id - pb-id; } int main() { scanf(%d%d, n, m); for (int i 0; i m; i) { scanf(%d, priority[i]); } Product *products (Product *)malloc(n * sizeof(Product)); for (int i 0; i n; i) { products[i].id i 1; products[i].attrs (int *)malloc(m * sizeof(int)); for (int j 0; j m; j) { scanf(%d, products[i].attrs[j]); } } qsort(products, n, sizeof(Product), cmp); for (int i 0; i n; i) { printf(%d\n, products[i].id); } for (int i 0; i n; i) { free(products[i].attrs); } free(products); return 0; }我在比较器里用了pa-id - pb-id来做最后的兜底这等价于稳定排序。当两个商品所有属性都相同时qsort也能保证按输入顺序输出因为id就是从输入顺序分配的。注意返回值没有用相减而是判断大小后返回-1或1从根源上规避了int溢出风险。4.7 六种语言横向对比语言代码量排序API稳定性是否需额外兜底Java中等Collections.sort稳定否Python最少list.sort(key)稳定否JS中等Array.sort稳定否Go中等sort.SliceStable稳定否C中等stable_sort稳定否C较多qsort不稳定是id兜底如果你的主语言是Python这道题几乎是在送分。用C语言写也能过但需要多花十分钟调试指针和动态内存。机考时间紧张时不建议用C语言写这种带结构体的排序题除非你已经非常熟练。5. 考场实战IO优化、边界条件与失分点清单5.1 输入解析的隐藏坑很多考生明明逻辑写对了却因为读入方式太慢导致大样例超时。这里给出各语言推荐的最快读入方式考前可以直接背下来。Java推荐BufferedReader StringTokenizerScanner在N等于10万的时候会明显变慢。Python推荐sys.stdin.buffer.read().split()不要用input()逐行读。JS用readline逐行收集数据不算大时问题不大。C用ios::sync_with_stdio(false)之后cin高速读取。C语言直接用scanf就很好。Go用bufio.Scanner。这里尤其要提醒Python考生很多人在本地练习时数据量小感觉不到区别一到机考大样例就开始卡。一次性read然后split其实代码也不复杂多写一行省下的时间非常可观。5.2 边界条件清单我建议写完代码后至少用下面这几种边界用例自测一遍N等于1只有一个商品排序结果必然是它自己检查代码不会因为比较器调用而出错。M等于1只有一个属性优先级列表只有一项逻辑简化后仍要能正确处理。所有商品的所有属性都相同此时必须输出1到N原始顺序。这会直接检验你的排序稳定性。属性值全部为负数或包含0比较器逻辑要正确不能用某种“取反”的取巧手段。属性值很大接近int上限C语言的差值比较写法要格外小心用判断大小代替相减。优先级列表里的下标值可能从1开始读题时确认是否需要减1。每一条都值得在本地跑一遍。尤其“所有属性相同”这条最容易暴露稳定排序问题。5.3 机考环境操作建议OD机考的答题界面通常支持在线编译但我个人的习惯是先在本地VS Code或IDEA里写完、跑通样例再复制到机考页面。原因很简单机考页面每次编译运行都要等队列反复提交很容易浪费时间。粘贴代码之后第一件事就是用自己的样例跑一遍确认输出格式完全一致。输出格式多一个空格、少一个换行在一些严格的判题系统里都会导致Wrong Answer。我见过一个考生因为最后一行多输出一个空行连续提交五次都不过最后才发现是格式问题。如果中途发现题目描述和你记的版本不一样比如属性下标从1开始或者要求降序不要慌直接把读到的priority值减一或者把比较器里的小于换成大于一分钟就能改完。这种“临时适配题面”的能力就是平时多刷题练出来的。6. 通用模板与备考建议一道题吃透一类排序题6.1 多属性排序的通用解题模板把这道题抽象一下你会发现它适用于很多场景学生按成绩、学号排序任务按优先级、截止时间排序订单按金额、时间排序。凡是“先按某个字段再按另一个字段”的需求核心逻辑都是同一个模板。第一步定义数据结构保存对象本身和其原始编号。第二步读取排序优先级列表。第三步实现比较函数遍历优先级列表逐个比较属性找到第一个不等的位置返回结果。第四步全部相等时返回0或者用原始编号兜底。第五步调用语言的稳定排序API。你只要把这个模板练熟以后遇到类似题目就是改数据结构的字段名而已不需要重新思考。6.2 备考阶段的刷题优先级如果距离机考还有两到三周我建议每天固定刷几类题字符串处理、数组模拟、排序与自定义比较器、二分查找、栈和队列。这些是机考的高频基础题型性价比极高。排序类题目尤其适合用来建立信心。因为它的思维量不大一旦你把某一种语言的比较器写法固定下来后面所有排序题都可以复用考试时基本是“秒写”。我备考时就把这个模板背到了肌肉记忆后来考场上遇到类似题花了不到十五分钟就写完并跑通全部用例。6.3 关于这道题的一点个人体会我在实际刷题过程中发现很多失分不是因为不会写比较器而是因为完全没意识到“稳定性”这个概念。你在本地用一个小样本测试碰巧没有重复属性排序结果自然正确可判题系统的测试用例可能全部设计成需要稳定排序的场景一提交就暴露问题。所以我会建议每一位备考的人练排序题的时候养成一个习惯写完代码先问自己一句“这个排序API稳定吗”。如果不稳定要么换成稳定版本要么在比较器里加id兜底。这个习惯看起来不起眼但真的能帮你避开很多隐藏的坑。最后再提一个小技巧考试前把你的主语言输入输出模板单独存成一个文件本地快速跑通后再进考场。这样一来你进考场后的第一件事不是回忆IO写法而是直接开始分析题目逻辑。这种准备方式比临时抱佛脚刷十道题都管用。