好像一次遍历就能出结果吧,为什么题解都是遍历两次的
查看原帖
好像一次遍历就能出结果吧,为什么题解都是遍历两次的
1240428
Sa_Zhi楼主2024/4/7 20:27
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define PII pair<int,int>
const int MAX = 10005;
int N,A[MAX],weizhi[MAX],ans=0;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>N;
	for(int i=1; i<=N; i++) {
		cin>>A[i];
		weizhi[A[i]] = i; //记录当前数的位置
	}
	for(int i=1; i<=N; i++) {
		if(weizhi[i]!=i) {
			A[weizhi[i]] = A[i];
			weizhi[A[i]] = weizhi[i];
			A[i] = i;
			weizhi[i] = i;
			ans++; 
		}
	}
	cout<<ans;
	return 0;
}
2024/4/7 20:27
加载中...