题解：P12176 [蓝桥杯 2025 省 Python B] 书架还原

这题主要的思想是贪心，与图论关系不大。

题目大意:

给你一个由

1

到

n

组成的序列，保证这

n

个数各不相同。请你求出将其从小到大排序的最少交换次数。

算法分析:

先看数据范围，

n

的最大值是

10^6

，暴力不可取。

考虑将无序数列中，每本书的下标记录下来，再

O(N)

扫一遍，找到放错的那些书。若第

i

本书放错位了，则将其应该在的位置上的书与其交换。

思路明确后，代码很简短。

AC Code:

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],b[1000005],ans;
int main(){
	scanf("%d",&n);//书架上有n本书。
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);//第i个位置上的书的编号。
		b[a[i]]=i;//记录其下标。
	}for(int i=1;i<=n;i++){
		if(b[i]!=i){//如果第i本书放错了，则需要调换一次。
			b[a[i]]=b[i];
			swap(a[b[i]],a[i]);
			ans++;
		}
	}
	printf("%d",ans);//输出最小交换次数。
	return 0;
}

题解：P12176 [蓝桥杯 2025 省 Python B] 书架还原

文章操作

题目大意:

算法分析:

AC Code:

相关推荐

评论

题解：P12176 [蓝桥杯 2025 省 Python B] 书架还原