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

题目描述

小团最近对逆序数（将一个数字逐位逆序，例如1234的逆序数为4321，1100的逆序数为11）特别感兴趣，但是又觉得普通的逆序数问题有点太乏味了。
于是他想出了一个新的定义：如果一个数的4倍恰好是它的逆序数，那么称这两个数是新定义下的逆序对。
接下来给定一正整数n，问：不超过n的正整数中有多少对新定义下的逆序对？

输入输出

输入描述
单组输入。
输入一个正整数n，n<1e7。
输出描述
第一行输出在不超过n的前提下有多少对逆序数，接下来每一行输出一对逆序数，以空格分隔。如果有多组逆序数，按照第一个数升序输出。
如果没有一对逆序数则直接输出0即可。

样例共 1 组

样例 1
输入
10000
输出
1
2178 8712

算法解析依据一般

考点：排序

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

题目画像

  • 数据规模：n ≤ 10000000
  • 复杂度门槛：只允许 O(n)：n 到千万量级时线性做法仍可行，但读入效率与常数要压紧；O(n log 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 ≤ 10000000，只允许 O(n)：n 到千万量级时线性做法仍可行，但读入效率与常数要压紧；O(n log n) 在此量级已偏紧。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：10000
  • 输出：1 / 2178 8712

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

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

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