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

_Z_YX_ · 2025-05-05 19:28:38 · 题解

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

题目大意:

给你一个由 1 到 n 组成的序列，保证这 n 个数各不相同。请你求出将其从小到大排序的最少交换次数。

算法分析:

先看数据范围， n 的最大值是 10^6，暴力不可取。

考虑将无序数列中，每本书的下标记录下来，再 O(N) 扫一遍，找到放错的那些书。若第 i 本书放错位了，则将其应该在的位置上的书与其交换。

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

AC Code:

#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;
}