AcWing 1224. 交换瓶子
原题链接
中等
作者:
季之秋
,
2021-03-15 22:10:44
,
所有人可见
,
阅读 325
/*
首先让每个点i指向应该出现位置上的值p[i]
1、同一个环内交换-->变成两个环
2、不同环内交换-->变成一个环
3、我们需要的结果是n个自环
由此得出最优解是交换同一个环直到总环数变成n个,即 :有多少个环(k) 则最少交换n-k次
然后st去维护哪些环遍历过? 没遍历过的一定是个新环
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),N=10010,res=0;
int p[]=new int[N]; boolean st[]=new boolean[N];
for(int i=1;i<=n;i++) p[i]=sc.nextInt();
for(int i=1;i<=n;i++)
if(!st[i]){
res++;
for(int j=i;!st[j];j=p[j]) st[j]=true;
}
System.out.println(n-res);
}
}