小团是一个做事很有规划的人。他列了在暑假期间要做的很多事情,对于每一件事情他都标注了优先级和必要程度,其中优先级从1到9,必要程度从1到5(数值越大,对应的优先级或者程度越高)。他希望对这些事情进行排序,排序规则如下: 必要程度大的事情排在前面;如果两件事情的必要程度一样则优先级大的排在前面;如果必要程度和优先级都一样则保持初始顺序不变。 因为事情实在是太多了,所以小团需要你的帮助。你能否编写一段代码来告诉小团这些事情的顺序呢?
单组输入。 第1行输入一个正整数n表示有n件需要完成的事情,这n件事情的初始编号分别为1、2、3、......、n。(n<=10000) 接下来n行,每行包含两个正整数a和b分别表示某一件事情的优先级和必要程度,两个数字之间用空格隔开。
输出按照要求排序后所有事情的初始编号,两个编号之间用空格隔开。
2 9 3 1 4
2 1
考点:排序
数据规模 n ≤ 1e4 | 限制 1 秒 / 256MB | 标准输入输出
参考方向:排序
先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。
思路框架(排序 通法 · 非本题专属)
实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。
复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
2 / 9 3 / 1 42 1解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:美团2023校招笔试-编程题(算法编程题)。