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

题目描述

请你开发一个美团商家测试系统，并用等价划分法确认商家注册信息是否成功。
商家信息必须满足以下条件：
1. 系统中第一次注册的商家名字，被视为主店。
2. 系统中若出现重名商家，需要判断地址是否已存在该商家。若存在，则注册失败。否则注册成功，该商家被视为分店。
3. 商家的名字和地址必须由小写的英文字母组成，否则注册失败。
请你输出每个商家的信息，按商家名字的字典序升序输出。需要输出商家名字，商家主店地址，商家分店数量。

输入输出

输入描述
第一行输入一个正整数 n ，代表注册信息数量。
接下来的 n 行，每行输入两个字符串，用空格隔开。分别代表商家名字和商家地址。
1≤ n ≤ 1000
给定的商家名字和商家地址字符串长度不超过 20，且不包含空格。
输出描述
按商家名字字典序输出全部商家信息。每行输出一个，分别输出商家名字，商家主店地址，商家分店数量，用空格隔开。

样例共 1 组

样例 1
输入
5
ranko mt
ranko op
ranko op
Ranko ok
red ok
输出
ranko mt 1
red ok 0

算法解析依据一般

考点：排序

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

题目画像

  • 数据规模：n ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，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 ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：5 / ranko mt / ranko op / ranko op / Ranko ok / red ok
  • 输出：ranko mt 1 / red ok 0

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

本题来源：2023年美团秋招编程岗第二批笔试。

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