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

wenqinghua1001 · 2025-05-02 21:19:06 · 题解

思路

我一看到这道题，认为是再求逆序对的个数，打了一个代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int ans=0;
int a[N],b[N],n;
void work(int l,int mid,int r){
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j])
            b[++k]=a[i++];
        else{
            b[++k]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid)
        b[++k]=a[i++];
    while(j<=r)
        b[++k]=a[j++];
    for(int i=l;i<=r;i++)
        a[i]=b[i-l+1];
}
void msort(int l,int r){
    if(l>=r) return ;
    int mid=(l+r)/2;
    msort(l,mid);
    msort(mid+1,r);
    work(l,mid,r);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    msort(1,n);
    cout<<ans;
    return 0;
}

逝世的测试信息。

我的天哪！我仔细理了一下题目，发现不是在求逆序对。

这道题要求书架上的书恢复到正确排列所需的最少操作次数，那么肯定要最优解，数据范围是 1 \le N \le 10^6，O(N^2) 肯定超时。

首先，第 i 个位置的数不是 i，一定要交换。换句话说，不该在相应位置的数肯定要交换，还要最优。那就要把两个都不符合条件的两个数交换位置，都变成正确的。

对重要结论的证明：我们发现这道题中不该在相应位置的位置，刚好形成了一个环，而且恰好每个环使用了 s−1 次边，交换了 s-1 次。时间复杂度是 O(N)。

代码

C++ 代码

AC 记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000001];
int b[10000001];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]; 
    for(int i=1;i<=n;i++)
        b[a[i]]=i;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=i){
            // 不符合条件。
            b[a[i]]=b[i];
            swap(a[i],a[b[i]]);
            // 把不符合条件的两个数位置交换。
            // 保证最优。 
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

Python 代码

AC 记录

n=int(input())
nums=list(map(int,input().split()))
ans=0
for i in range(n):
    while nums[i]!=i+1 :
        # 不符合条件。
        j=nums[i]-1
        tmp=nums[j]
        nums[j]=nums[i]
        nums[i]=tmp
        # 把不符合条件的两个数位置交换。
        # 保证最优。 
        ans+=1
print(ans)