1000ms

Difficulty: 7

所属公司 : 阿里

时间 :2025年5月12日-阿里国际(开发岗)

算法与标签>构造

会员专享

请先登录，开通会员或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

题解

问题描述

给定一个长度为 $n$ 的排列 $p = [p_1, p_2, \dots, p_n]$ 。称下标 $i$ （ $1 \le i < n$ ）为“好位置”，如果存在 $j$ 满足 $i < j \le n$ 且 $p_i > p_j$ 。记原排列中“好位置”的个数为 $G(p)$ 。

要求构造另一个排列 $q$ ，满足：

$q \neq p$ ；

题目内容

小苯定义一个数组的“好位置”为：满足其右侧存在比其小的元素形式化的即:

在数组 $a$ 中对于 $1≤i<n$ 存在 $1≤i<j≤n$ 使得 $a_i>a_j$ ，则称 $i$ 为“好位置”。

现在小苯有一个长度为 $n$ 的排列 $p$ ，他希望你构造一个长为n的排列 $q$ ，满足 $p≠q$ 同时 $p,q$ 的“好位置”个数相同。