nums = [3, 2, 1]
cost_adj = 1, cost_any = 3

使序列递增的最小交换次数（进阶版：允许相邻交换和任意位置交换，但有交换代价） 问题描述 给定一个长度为n的整数数组 nums ，你可以进行两种操作： 相邻交换：交换任意相邻的两个元素，每次交换代价为 cost_adj 。 任意交换：交换任意两个位置的元素，每次交换代价为 cost_any 。 你的目标是通过最少的交换次数（或最小总代价），使得数组变成严格递增的。如果无法实现，则返回 -1 。 示例： 我们可以通过两次相邻交换（交换(3,2)然后交换(3,1)）使数组变成[ 1,2,3]，总代价为2* 1=2。或者通过一次任意交换（交换位置0和2）变成[ 1,2,3 ]，代价为3。最小代价是2。 解题思路 这是一个 序列排序+交换代价优化 的问题。我们首先需要明确： 如果数组元素可以任意重排，那么严格递增的唯一可能，就是数组排序后是严格递增的（即没有重复元素）。 但本题中，数组元素是给定的，可能存在重复元素，如果排序后不是严格递增（有重复），则直接返回 -1 ，因为严格递增要求所有元素不同。 核心难点 ：如何在允许两种交换操作，且代价不同的情况下，以最小代价将数组变成严格递增。 我们可以拆解为以下步骤： 步骤1：预处理和可行性判断 对数组 nums 进行排序，得到 sorted_nums 。 检查 sorted_nums 是否严格递增（即 sorted_nums[i] < sorted_nums[i+1] 对所有i成立）。如果不是，说明存在重复元素，无法变成严格递增，直接返回 -1 。 步骤2：重新理解问题 问题转化为： 将原数组通过交换操作，变成排序后的数组（严格递增），求最小交换代价 。这本质上是一个 最小交换次数使数组有序 的问题，但加入了两种交换方式，且代价不同。 我们考虑从原数组到目标数组的映射。因为数组元素可能重复，但排序后严格递增，所以每个值在原数组中出现的位置是唯一的吗？不，如果原数组有重复，则无法严格递增，所以我们已在步骤1排除了这种情况。因此， 每个值在原数组中只出现一次 ，这样我们可以建立从“值”到“目标位置”的一一映射。 更具体地： 目标数组是 sorted_nums ，其中 sorted_nums[i] 应该放在位置i。 对于原数组 nums[j] ，我们找到它在排序后数组中的目标位置 pos[j] ，即 sorted_nums 中等于 nums[j] 的元素的下标（因为无重复，所以唯一）。 这样，我们得到一个 位置映射数组 pos ，长度为n， pos[j] 表示原数组位置j的元素应该被放到目标位置 pos[j] 。 问题进一步转化为 ：我们有一个排列 pos （因为每个目标位置恰好出现一次），我们希望通过交换操作，将这个排列变成恒等排列 [0,1,2,...,n-1] ，每次交换的代价取决于交换类型。 步骤3：两种交换操作的图论模型 将排列 pos 看作一个置换，可以分解成若干个循环（cycle）。例如 pos = [2,0,1] ，表示： 位置0的元素应该去位置2， 位置1的元素应该去位置0， 位置2的元素应该去位置1。 这是一个长度为3的循环：0→2→1→0。 经典结论 ：对于一个长度为k的循环，如果只允许相邻交换（即交换相邻元素），那么将这个循环还原（即循环内所有元素归位）所需的最小相邻交换次数是多少？实际上，对于排列的循环，用相邻交换还原整个排列的最小交换次数是 n - c ，其中c是循环的个数。但这里我们只针对一个循环，最小相邻交换次数是 k-1 吗？并不是简单的公式，因为相邻交换每次只能交换相邻位置的元素，而循环内的元素可能不是相邻的。 我们需要更精确的模型：我们可以将问题看作 通过交换操作，将循环内的元素归位 。对于相邻交换，我们可以用 逆序数 来考虑，但这里循环内的元素是任意分布的，相邻交换的代价与循环内元素的相邻距离有关，计算复杂。 另一种思路 ：既然我们有两种交换操作，且任意交换代价固定，相邻交换代价固定，我们可以考虑 对每个循环，选择最优的交换策略 。 对于一个长度为k的循环（k≥2），我们可以用两种方式将其归位： 全部用相邻交换 ：但如何计算将一个循环还原所需的最小相邻交换次数？这等价于：对于循环内的元素，我们希望通过交换相邻元素，使得每个元素到达其目标位置。这可以看作是一个 最小交换次数使数组有序 的问题，但仅限于循环内的元素。实际上，如果只考虑循环内的元素，并且只允许相邻交换，那么最小交换次数等于循环内元素的逆序数（相对于它们在目标顺序中的位置）。计算这个逆序数需要将循环提取出来单独处理，时间复杂度O(k²)或O(k log k)。 全部用任意交换 ：对于一个长度为k的循环，用任意交换将其归位的最小次数是 k-1 （每次交换可以将一个元素放到正确位置，最后一次自然归位）。总代价 = (k-1) * cost_any 。 混合策略 ：也可以部分用相邻交换，部分用任意交换，但这样不会更优，因为任意交换一次可以解决任意两个位置，而相邻交换可能需要多次才能达到同样效果。通常，最优策略是在“全用相邻交换”和“全用任意交换”之间取优。 但这里有一个关键点：相邻交换的代价可能与元素间的距离有关吗？题目中给定的 cost_adj 是每次交换的代价， 与交换的相邻元素的位置无关 。所以，我们只需要比较用相邻交换的总代价 vs 用任意交换的总代价。 因此，问题简化为 ：对于每个循环，计算“用相邻交换将循环归位的最小交换次数”，乘以 cost_adj ，得到这个循环用相邻交换的代价；用任意交换的代价是 (k-1) * cost_any 。取两者较小值，然后对所有循环求和。 步骤4：计算一个循环用相邻交换归位的最小交换次数 考虑一个循环，包含位置集合C = {i₁, i₂, ..., iₖ}，且这些位置上的元素应该被移动到目标位置集合C' = {pos[ i₁], pos[ i₂], ..., pos[ iₖ ]}，且C' = C（因为循环是位置的置换）。实际上，循环内的元素就是在这些位置上轮换。 例如循环0→2→1→0，即位置0,2,1上的元素需要轮换。初始位置：[ 0,1,2 ]上的元素分别是a,b,c，但根据pos，a应该去位置2，b应该去位置0，c应该去位置1。即初始位置0,1,2上的元素分别是a,b,c，目标位置0,1,2上应该分别放b,c,a。 我们只关心这些位置上的元素，将循环单独提取出来，形成一个长度为k的子数组，其下标是循环中的位置顺序（按循环顺序），但我们需要知道这些位置在原始数组中的相邻关系，因为相邻交换只能交换原始数组中相邻位置的元素。 重要观察 ：相邻交换是在原始数组的相邻位置上进行的，而循环中的位置可能在原始数组中不相邻。例如，循环包含位置0和位置5，它们不相邻，不能直接交换。要交换它们，需要通过一系列相邻交换，将元素逐步移动到目标位置。 因此， 用相邻交换将一个循环归位，等价于通过相邻交换，将循环中所有元素移动到它们的目标位置 。这可以转化为：我们有一个数组，其中某些位置是“错误”的，我们需要通过交换相邻元素，使得每个元素到达正确位置。这实际上就是 冒泡排序 的过程：最小交换次数等于数组中逆序对的数量（这里逆序对是针对元素的目标位置顺序而言的）。 具体方法： 提取循环中的位置，按照它们在原始数组中的位置顺序排序，得到列表L = [ p₁, p₂, ..., pₖ ]（递增）。 对于L中的每个位置p_ j，我们知道它上面的元素应该去的目标位置是pos[ p_ j]。但注意，目标位置也在这个循环中，且可能不在L的顺序中。我们需要将L中的元素，通过交换相邻元素，使得第j个位置上的元素最终位于目标位置pos[ p_ j ]在L中的对应位置？这有点绕。 更简单的方法：我们直接考虑原始数组，但只关注循环涉及的元素。我们想要计算，如果只允许相邻交换，将整个数组变成有序的最小交换次数。这个次数等于 数组中逆序对的数量 （因为数组元素不同）。但这里，我们只关心将循环归位，而循环外的元素已经在正确位置，所以实际上，整个数组的逆序对数，就是由于循环内的元素错位引起的。因此， 用相邻交换将整个数组排序的最小交换次数 = 整个数组的逆序对数 。而整个数组的逆序对数，可以通过树状数组或归并排序在O(n log n)时间内计算。 结论 ：对于整个数组，用相邻交换将其排序的最小交换次数 = 逆序对数。那么，对于单个循环，如果我们用相邻交换只将这个循环归位，而其他位置不变，其最小交换次数是否等于“整个数组逆序对数”减去“其他循环引起的逆序对数”？这不太容易直接计算。 更精确的做法 ：我们可以直接计算，如果只允许相邻交换，将整个数组变成有序的最小交换次数 = 逆序对数。而这个值，对于所有循环整体而言，就是每个循环内部归位所需的相邻交换次数的总和吗？是的，因为不同循环之间的元素没有交叉逆序（因为循环是独立的置换），所以总的逆序对数等于各个循环内部的逆序对数之和。因此，我们可以 分别计算每个循环内部的逆序对数 ，然后乘以 cost_adj ，得到这个循环用相邻交换的代价。 如何计算一个循环内部的逆序对数 ？ 给定循环C = {i₁, i₂, ..., iₖ}，我们需要计算，如果只考虑这些位置上的元素，将它们排成正确顺序（即目标位置顺序）所需的最小相邻交换次数。注意，这些位置在原始数组中可能不连续，但相邻交换只能在原始数组的相邻位置进行，所以我们不能简单地将这些位置提取出来单独排序，因为交换可能涉及到循环外的元素？实际上，由于我们只交换相邻元素，交换操作可能会涉及到循环外的元素，但循环外的元素已经在正确位置，交换它们可能会破坏正确性。所以，我们不能只孤立地考虑循环内的位置。 这个难题使得我们重新思考：也许我们不需要计算每个循环的逆序对数，而是直接计算整个数组的逆序对数，然后乘以 cost_adj ，就是全用相邻交换的总代价。然后，全用任意交换的总代价是 (n - c) * cost_any ，其中c是循环的个数（因为每个长度为k的循环需要k-1次任意交换，总和为n-c）。 这样，我们只需要比较： 全用相邻交换的代价： inv_count * cost_adj 全用任意交换的代价： (n - c) * cost_any 取两者较小值即可。 但这是否正确 ？考虑一个例子：nums = [ 3,2,1]，排序后[ 1,2,3]。位置映射pos = [ 2,1,0]（因为3应该去位置2，2去位置1，1去位置0）。这个排列是一个长度为3的循环（0→2→0？实际上0→2→1→0，是长度为3的循环）。逆序对数：整个数组的逆序对数是3（(3,2),(3,1),(2,1)）。全用相邻交换的代价 = 3 * cost_ adj。全用任意交换的代价 = (3-1) cost_ any = 2 cost_ any。当cost_ adj=1, cost_ any=3时，3 1=3 vs 2 3=6，相邻交换代价更小，为3。但实际最小代价是2（通过两次相邻交换）。为什么有差异？因为用相邻交换排序整个数组的最小交换次数是逆序对数=3，但实际上我们可以用更少的次数？不，对于[ 3,2,1]，用相邻交换（冒泡排序）最小需要交换3次（交换(3,2)得[ 2,3,1]，交换(3,1)得[ 2,1,3]，交换(2,1)得[ 1,2,3]）。但之前示例中说通过两次相邻交换就可以？错了，仔细看：示例中交换(3,2)然后交换(3,1)得到[ 1,2,3]？实际上，交换位置0和1（3和2）得到[ 2,3,1]，再交换位置0和2（2和1）得到[ 1,3,2]，再交换位置1和2（3和2）得到[ 1,2,3 ]，需要三次。所以示例中的解释有误，两次交换不可能。所以逆序对数是3，正确。所以我们的公式一致。 因此，全用相邻交换的最小代价 = 逆序对数 * cost_ adj。 步骤5：算法步骤总结 检查数组排序后是否严格递增，如果不是（有重复），返回-1。 获取排序后的数组sorted_ nums，并为原数组每个值找到其在sorted_ nums中的目标位置，得到位置映射数组pos。 找出排列pos中的所有循环，计算循环个数c，并计算每个循环的长度。 计算整个数组的逆序对数inv_ count（相对于sorted_ nums的顺序，即数组元素在排序数组中的排名顺序）。 全用相邻交换的总代价 = inv_ count * cost_ adj。 全用任意交换的总代价 = (n - c) * cost_ any。 返回 min(全用相邻交换代价, 全用任意交换代价)。 注意 ：我们假设了两种操作不能混合使用，因为混合使用不会更优吗？考虑一个循环，部分用相邻交换，部分用任意交换，可能比全用一种更优？例如，cost_ adj很小，cost_ any很大，但循环中有些元素相距很远，用相邻交换代价很高，也许可以用一次任意交换将其归位，其余用相邻交换。但这样，一次任意交换可以替代多次相邻交换，但任意交换代价可能很高。我们需要比较：对于长度为k的循环，用相邻交换的代价是inv_ k * cost_ adj，用任意交换的代价是(k-1) cost_ any。但inv_ k可能大于k-1（通常逆序对数最多为k (k-1)/2）。如果cost_ adj远小于cost_ any，但inv_ k很大，也许混合策略更好：用一次任意交换将某个元素放到正确位置，可能减少逆序对，从而减少相邻交换次数。但这样分析复杂。然而，由于任意交换一次可以任意调整两个元素，我们可以认为，对于每个循环，最优策略要么全用相邻交换，要么全用任意交换。因为如果混合，我们可以将一次任意交换替换为若干次相邻交换，或者反过来，总代价不会更优。因此，我们只需比较两种纯策略。 步骤6：计算逆序对数 逆序对数计算：将原数组元素映射为其在排序数组中的索引（排名），因为严格递增，所以排名是唯一的。然后计算这个排名数组的逆序对数。用树状数组或归并排序，时间复杂度O(n log n)。 步骤7：计算循环 通过visited数组，遍历pos数组，找出所有循环，并统计循环个数c。 步骤8：最终答案 ans = min(inv_ count * cost_ adj, (n - c) * cost_ any) 示例验证 例1：nums = [ 3,2,1], cost_ adj=1, cost_ any=3 排序后[ 1,2,3 ]严格递增。 pos: 3的目标位置2, 2的目标位置1, 1的目标位置0 -> pos=[ 2,1,0 ] 循环：0->2->1->0，一个循环，c=1, n-c=2。 排名数组：原数组[ 3,2,1 ]的排名分别是2,1,0。逆序对：(2,1),(2,0),(1,0)共3个。 全相邻交换代价=3 1=3，全任意交换代价=2 3=6，取min=3。 实际最小代价为3（三次相邻交换），正确。 例2：nums = [ 1,3,2,4], cost_ adj=5, cost_ any=2 排序后[ 1,2,3,4 ]严格递增。 pos: 1->0, 3->2, 2->1, 4->3 -> pos=[ 0,2,1,3 ] 循环：位置0自身循环，位置1和2形成循环(1,2)，位置3自身循环。c=3（三个循环：长度1,2,1），n-c=1。 排名数组：[ 1,3,2,4] -> 排名[ 0,2,1,3 ]。逆序对：(2,1) 一个。 全相邻交换代价=1 5=5，全任意交换代价=1 2=2，取min=2。 实际：用一次任意交换交换位置1和2，代价2，得到[ 1,2,3,4 ]。正确。 复杂度分析 时间复杂度：O(n log n)，来自排序和计算逆序对数。 空间复杂度：O(n)，用于存储排名、pos等。 扩展思考 如果允许混合使用两种交换，并且每次交换代价可能不同（例如相邻交换代价与位置有关），问题会更复杂，可能需要用动态规划或图的最优置换算法。本题简化了代价模型，使得可以分别计算两种策略取最优。