1067 Sort with Swap(0, i) (25 分)

举个例子,有以下数据

i	0	1	2	3	4
a[i]	0	4	3	2	1

根据线性代数知识，可以分成{0}，{1，4}，{2，3}三组。
记包含0的组合的个数为 n 0 n_0 n0​,每个不包含0的组合为 n i n_i ni​
在包含0的组合交换次数为 n 0 − 1 n_0-1 n0​−1次,不包含0的组合需要先将0换入，然后交换 ( n i + 1 ) − 1 (n_i+1)-1 (ni​+1)−1次，再将0换出，即 n i + 1 n_i+1 ni​+1次
交换总次数= ( ∑ i = 0 n n i + 1 ) − 2 (\sum_{i=0}^nn_i+1)-2 (∑i=0n​ni​+1)−2
代码思想：通过circle数组标记已访问过的组合，cnt记录circle数组元素个数。

#include<cstdio>
#include<cstring>
int a[100005];
int t[100005];   //记录元素i的位置
bool circle[100005];
int main()
{
	memset(circle,false,sizeof(circle));
	int n,cnt=0,p,time;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		t[a[i]]=i;
	}
	for(int i=0;i<n;i++)
	{
		p=i;
		if(circle[p]||a[i]==i) continue;
		time=0;
		while(circle[p]==false)
		{
			circle[p]=true;
			p=t[p];
			time++; 
		}
		if(i==0) time-=1;
		else time+=1;
		cnt+=time;
	}
	printf("%d",cnt);
	return 0;
}