蓝桥杯每日一题2023.11.20-CSDN博客

题目描述

“蓝桥杯”练习系统 (lanqiao.cn)

题目分析

方法一暴力枚举如果说数字不在正确的位置上也就意味着这个数必须要改变进行改变记录即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], ans;
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)cin >> a[i];
	for(int i = 1; i <= n; i ++)
	{
		if(a[i] != i)
		{
			for(int j = i + 1; j <= n; j ++)
			{
				if(a[j] == i)
				{
					swap(a[i], a[j]);
					ans ++;
				}
			}
		}
	}
	cout << ans;
	return 0;
}

方法二置换群算法每个数字和对应位置相连可以组成一个环如果说每个数字可以形成自环也就说明每一个数字都在自己正确的位置上我们可以找出有几个环n - 环的个数则为需要交换的个数。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, cnt;
bool st[N];
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)cin >> a[i];
	for(int i = 1; i <= n; i ++)
	{
		if(!st[i])
		{
			cnt ++;
			for(int j = i; !st[j]; j = a[j])
			{
				st[j] = true;
			}
		}
	}
	cout << n - cnt;
	return 0;
}