暴力做法
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
int cnt = 0;
for (int i = 1, j = 1; i <= n-1; i++)
{
if (a[i] != i)
{
j = i + 1;
while (a[j] != i)j++;
swap(a[i], a[j]);
cnt++;
/*cout << i << " " << j << endl;
for (int i = 1; i <= n; i++)cout << a[i] << " ";
puts("");*/
}
}
cout << cnt << endl;
}
图论做法
先找原本有(cnt)几个环。
每交换一次环中两点,环就会裂成两个。
目标是变成n个环,就是每个数都是自环。
交换n-cnt次。
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int b[N];
bool st[N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)scanf("%d", &b[i]);
int cnt = 0;//找有几个环
for (int i = 1; i <= n; i++)
if (!st[i])
{
cnt++;
for (int j = i; !st[j]; j = b[j])
st[j] = true;
}
cout << n - cnt << endl;
}