美团 · 排序 · 算法编程题
美团 排序 n ≤ 1e4 时限 1 秒 / 256 MB

题目描述

小团是一个做事很有规划的人。他列了在暑假期间要做的很多事情,对于每一件事情他都标注了优先级和必要程度,其中优先级从1到9,必要程度从1到5(数值越大,对应的优先级或者程度越高)。他希望对这些事情进行排序,排序规则如下:
必要程度大的事情排在前面;如果两件事情的必要程度一样则优先级大的排在前面;如果必要程度和优先级都一样则保持初始顺序不变。
因为事情实在是太多了,所以小团需要你的帮助。你能否编写一段代码来告诉小团这些事情的顺序呢?

输入输出

输入描述
单组输入。
第1行输入一个正整数n表示有n件需要完成的事情,这n件事情的初始编号分别为1、2、3、......、n。(n<=10000)
接下来n行,每行包含两个正整数a和b分别表示某一件事情的优先级和必要程度,两个数字之间用空格隔开。
输出描述
输出按照要求排序后所有事情的初始编号,两个编号之间用空格隔开。

样例共 1 组

样例 1
输入
2
9 3
1 4
输出
2 1

算法解析依据一般

考点:排序

数据规模 n ≤ 1e4 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:n ≤ 1e4
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:排序

先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。

思路框架(排序 通法 · 非本题专属)

  1. 排序后很多性质变简单:相邻关系、前缀性质、二分可行。
  2. 若题目禁止使用排序库函数,则手写快排/归并(归并还能顺带求逆序对)。
  3. 排序常与其他范式组合,比如「排序 + 贪心」「排序 + 二分」「排序 + 双指针」。

实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。

复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)

该范式的通法易错点

  • 自定义比较函数不满足严格弱序会导致运行时崩溃。
  • 排序后丢失原始下标,题目需要下标时记得用 pair 一起排。

对照本题

  • 数据规模 n ≤ 1e4,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:2 / 9 3 / 1 4
  • 输出:2 1

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:美团2023校招笔试-编程题(算法编程题)。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解