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

题目描述

小团是美团外卖的区域配送负责人,众所周知,外卖小哥一般都会同时配送若干单,小团在接单时希望把同一个小区的单子放在一起,然后由一名骑手统一配送。但是由于订单是叠在一起的,所以,他归类订单时只能知道新订单和已有的某个订单的小区是相同的,他觉得这样太麻烦了,所以希望你帮他写一个程序解决这个问题。
即给出若干个形如a b的关系,表示a号订单和b号订单是同一个小区的 ,请你把同一个小区的订单按照编号顺序排序,并分行输出,优先输出最小的订单编号较小的小区订单集合。订单的编号是1到n。(可能存在同时出现a b和b a这样的关系,也有可能出现a a这样的关系)

输入输出

输入描述
输入第一行是两个正整数n,m,表示接受的订单数量和已知的关系数量。(1<=n,m<=10000)
接下来有m行,每行两个正整数a和b,表示a号订单和b号订单属于同一个小区(1<=a,b<=n);
输出描述
输出第一行包含一个整数x,表示这些订单共来自x个不同的小区。
接下来的输出包含x行,每行表示输出若干个订单编号,表示这些订单属于同一个小区,按照订单编号升序输出。优先输出最小的订单编号较小的小区。

样例共 1 组

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

算法解析依据一般

考点:排序

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

题目画像

  • 数据规模:m ≤ 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 一起排。

对照本题

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

样例

样例 1

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

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

本题来源:美团2023校招技术第2场编程题。

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