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

题目描述

小美定义一个数组 a 的权值计算如下：
首先将 a 的每一对相邻两项求和，得到一个 b 数组。那么 b 数组的最大值减最小值即为 a 数组的权值。
例如，若 a=[2,1,3] ，那么 b=[3,4] ， b 数组的极差是1。因此 a 数组的权值为1。
现在小美希望你能构造一个长度为 n 的排列，满足权值尽可能小。你能帮帮她吗？
排列是指一个长度为 n 的数组，其中 1 到 n 每个元素恰好出现一次。

输入输出

输入描述
一个正整数 n ，代表排列的长度。
2≤ n ≤ 200000
输出描述
一个合法的排列。如果有多解输出任意即可。

样例共 1 组

样例 1 · 这个数组的权值为 1。输出[2,3,1]等排列也是合法的。
输入
3
输出
2 1 3

算法解析依据一般

考点：构造

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

题目画像

  • 数据规模：n ≤ 200000
  • 复杂度门槛：只允许 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：输入 3 → 输出 2 1 3

这个数组的权值为 1。输出[2,3,1]等排列也是合法的。

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

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

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