给定一个长度为 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 ,表示你构造的排列。若存在多个解,输出任意一个,系统会自动判定是否正确。
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 | 标准输入输出
参考方向:构造
不要求唯一答案,只需按规则造出一个合法解,常从边界/特殊情形入手。
思路框架(构造 通法 · 非本题专属)
实现要点:构造题不判最优,只判合法性,因此验证环节不能省。
复杂度:时间 O(n) | 空间 O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
2 / 5 / 1 2 4 3 5 / 4 / 1 4 2 31 2 3 4 5 / 1 2 4 3解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2026年春招-美团-测试岗-第一批笔试。