当前没有测试数据。

由0、1、2组成的序列最少交换次数题解

一、题目深度分析

1. 题目核心要求

给定一个仅由0、1、2组成的长度为n的序列，通过交换任意两个数的操作将其变为单调不递减序列，求完成目标所需的最少交换次数。

2. 单调不递减的最终形态

由于序列仅包含0、1、2，其单调不递减的最终形态必然是先全部0，接着全部1，最后全部2。例如：

• 若序列中0的个数为cnt0，1的个数为cnt1，2的个数为cnt2，则最终序列的划分是：
  • 0区：第1 ~ cnt0个位置，只能是0；
  • 1区：第cnt0+1 ~ cnt0+cnt1个位置，只能是1；
  • 2区：第cnt0+cnt1+1 ~ n个位置，只能是2。

3. 问题本质：统计错位元素并优化交换

交换的核心是用最少的次数修正所有错位元素。由于交换两个元素可同时修正两个错位（若为“互相错位”），因此需优先处理这类情况，剩余的错位则为“循环错位”，需额外处理。

二、关键统计指标

我们需要统计每个区域中出现的非本区元素数量，定义如下：

1. 0区的错误：
   • x1：0区中出现的1的数量；
   • x2：0区中出现的2的数量；
2. 1区的错误：
   • y0：1区中出现的0的数量；
   • y2：1区中出现的2的数量；
3. 2区的错误：
   • z0：2区中出现的0的数量；
   • z1：2区中出现的1的数量。

三、最少交换策略

交换分为一次解决两个错误和两次解决一个循环错误两类，优先级依次降低：

1. 优先处理“互相错位”（一次交换解决两个错误）

• 类型1：0区的1（x1）和1区的0（y0）互相错位。交换一次可同时修正一个x1和一个y0，次数为min(x1, y0)。
• 类型2：0区的2（x2）和2区的0（z0）互相错位。交换一次可同时修正一个x2和一个z0，次数为min(x2, z0)。
• 类型3：1区的2（y2）和2区的1（z1）互相错位。交换一次可同时修正一个y2和一个z1，次数为min(y2, z1)。

2. 处理“循环错位”（两次交换解决一个错误）

剩余的错位会形成三元循环（如0区的1→1区的2→2区的0→0区的1），这类循环中每个错误需要两次交换才能修正，剩余错误总数为x1 + x2（剩余的0区错误），因此需增加(x1 + x2) * 2次交换。

四、样例实战分析

样例1

输入：5 ；2 0 1 2 0 步骤1：统计数量：cnt0=2，cnt1=1，cnt2=2。 步骤2：划分区域：0区（1-2）、1区（3）、2区（4-5）。 步骤3：统计错位：

• 0区：位置1是2（x2=1），位置2是0（正确）→ x1=0，x2=1；
• 1区：位置3是1（正确）→ y0=0，y2=0；
• 2区：位置4是2（正确），位置5是0（z0=1）→ z0=1，z1=0。 步骤4：计算交换次数：
• 类型1：min(0,0)=0；
• 类型2：min(1,1)=1（交换0区的2和2区的0，完成修正）；
• 类型3：min(0,0)=0；
• 循环错位：0+0=0，无需额外交换。 最终结果：1（与样例输出一致）。

样例4

输入：3 ；2 0 1 步骤1：统计数量：cnt0=1，cnt1=1，cnt2=1。 步骤2：划分区域：0区（1）、1区（2）、2区（3）。 步骤3：统计错位：

• 0区：位置1是2（x2=1）→ x1=0，x2=1；
• 1区：位置2是0（y0=1）→ y0=1，y2=0；
• 2区：位置3是1（z1=1）→ z0=0，z1=1。 步骤4：计算交换次数：
• 类型1：min(0,1)=0；
• 类型2：min(1,0)=0；
• 类型3：min(0,1)=0；
• 循环错位：0+1=1，需1*2=2次交换。 最终结果：2（与样例输出一致）。

五、代码详细注释