美团 · 构造 · 算法编程题
美团 构造 n ≤ 200000 时限 1 秒 / 256 MB

题目描述

给定一个长度为 n 的排列 a_1, a_2, ..., a_n ,Tk 希望你构造一个长度同为 n 的排列 b_1, b_2, ..., b_n ,使得构造后得到的数组 c_1, c_2, ..., c_n 是单调不降的,其中 c_i = a_i + b_i 。
请输出你构造的排列 b 。可以证明在题目限制内总有解。
排列:长度为 n 的排列是由 1 n 这 n 个整数按任意顺序组成的数组,其中每个整数恰好出现一次。
单调不降:对于数组 c_i ,如果对任意 1 ≤ i < n ,都有 c_i ≤ c_i+1 ,则称其为单调不降数组。

输入输出

输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1 ≤ T ≤ 10^4) ,代表数据组数,每组测试数据描述如下:
第一行输入一个整数 n(1 ≤ n ≤ 2 × 10^5) ,表示数组长度;
第二行输入 n 个整数 a_1, a_2, ..., a_n(1 ≤ a_i ≤ n) ,表示排列 a_i 。
除此之外,保证单个测试文件中所有 n 的总和不超过 2 × 10^5 。
输出描述
对于每组测试数据,新起一行输出 n 个整数 b_1, b_2, ..., b_n ,表示你构造的排列。若存在多个解,输出任意一个,系统会自动判定是否正确。

样例共 1 组

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

算法解析依据一般

考点:构造

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

题目画像

  • 数据规模:n ≤ 200000,T ≤ 1e4
  • 复杂度门槛:只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:构造

不要求唯一答案,只需按规则造出一个合法解,常从边界/特殊情形入手。

思路框架(构造 通法 · 非本题专属)

  1. 先看最小的几个规模(n=1,2,3)手工构造,找规律。
  2. 尝试用「重复某种模式」或「从特殊到一般」的方式拼出答案。
  3. 构造完成后必须验证:写一个暴力或直接对照题目条件检查一遍。
  4. 注意题目对「多解」的输出要求(任意一个合法解即可)。

实现要点:构造题不判最优,只判合法性,因此验证环节不能省。

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

该范式的通法易错点

  • 构造出的解不满足全部约束(漏了隐藏条件)。
  • 输出格式与题目要求不一致(多解题也要求格式严格)。

对照本题

  • 数据规模 n ≤ 200000,只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

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

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

本题来源:2026年春招-美团-测试岗-第一批笔试。

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