解题思路:
算法1-置换群算法
将每一个瓶子看成图中的一个点
连接的方式是把我们当前的位置的 a[i]
连向我们本该在的位置的 a[i]
,(也可以理解为每 个i
都连向它的a[i]
,乱序的时候)
所以一共会有n
各个点,n
条边,每个点的出度是1
,入度也是1
所以这样的图里面必然是一堆环,最终希望变成5个自环。
每次交换任意两个数,必然只有两种操作
一种是把一个环分裂成两个,一种是把两个环合成一个。
初始时假设有k
个环,最终希望变成n
个环,每次操作最多只能增加一个环(1个环变成2个),所以我们最少需要用n-k
次操作,才能把k
个环变成n
个环,而且只要有一个环存在2
个以上的点包括2
个,就必然可以交换这个环中的数使其分解,所以必然存在一种方案,使得恰好交换n-k
次就可以把k
个环裂成n个
答案必定>=n-k
,可以取到n-k
,一定有一种方案,一直交换同一个环内的点,也就是一直分解,不去做合并的操作(情况2),因为就这两个操作,所以一定可以取到最小值n-k
所以这道题的本质就是求一下初始的环数k
,n-k
即是至少交换的次数
代码(Java)
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static final int N = 10010;
static int[] b = new int[N]; //b[i]表示i位置存的是哪个瓶子
static boolean[] st = new boolean[N]; //st[]表示该瓶子在找环时,已经被找过了
public static void main(String[] args ) throws IOException {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1; i <= n; i ++ ) b[i] = scan.nextInt();
int cnt = 0; //统计初始环数k
for(int i = 1; i <= n; i ++ )
{
if(! st[i]) //如果当前瓶子没被找到过,说明环数 +1
{
cnt ++; //环数 +1
for(int j = i; !st[j]; j = b[j]) //并把i瓶子所在环的所有瓶子都标记为true
st[j] = true; //瓶子j指向的点是j这个位置上的数
}
}
System.out.println(n - cnt);
}
}
算法2-暴力枚举
- 每一个数必须回到它自己的位置上,比如1必须在第1位,2必须在第2位
- 那么我们就可以这样操作,由于每个数必须回到自己的位置,直接从
1
枚举到n
,如果当前位置的数不等于它的下标,那么我们就必须要把它给替换掉 - 设当前位置为
i
的话,那么我们就从i+1
开始往后枚举,直到找到对应的a[j]
和我们的i
相等,交换两数,交换次数cnt++
- 容易证明这个算法的正确性,由于每个数必须回到原来的位置,所以我们这样子操作不会出现多于的步骤,因为每次操作都是必须的
代码(Java)
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static final int N = 10010;
static int[] b = new int[N]; //b[i]表示i位置存的是哪个瓶子
public static void main(String[] args ) throws IOException {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1; i <= n; i ++ ) b[i] = scan.nextInt();
int cnt = 0; //交换次数
for(int i = 1; i <= n; i ++ )
{
if(i != b[i]) //如果当前位置的数不等于其下标编号,那么去其后面找对应的b[j],交换二者即可
{
for(int j = i + 1; j <= n; j ++ )
{
if(b[j] == i)
{
int t = b[i];
b[i] = b[j];
b[j] = t;
cnt ++;
}
}
}
}
System.out.println(cnt);
}
}
因为题给数据范围是
1~10000
,所以O(n^2)
不会超时
参考文献: 来源