网站开发费用如何入账,网络运营管理,青岛建站培训,揭阳cms建站题目描述
“蓝桥杯”练习系统 (lanqiao.cn) 题目分析
方法一#xff1a;暴力枚举#xff0c;如果说数字不在正确的位置上也就意味着这个数必须要改变#xff0c;进行改变记录即可
#includebits/stdc.h
using namespace std;
const int N 2e5 10;
int n, a[N], …题目描述
“蓝桥杯”练习系统 (lanqiao.cn) 题目分析
方法一暴力枚举如果说数字不在正确的位置上也就意味着这个数必须要改变进行改变记录即可
#includebits/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 - 环的个数则为需要交换的个数。 #includebits/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;
}
