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

思路

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

CPP

#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 记录

CPP

#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 记录

PYTHON

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)

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

文章操作

思路

代码

C++ 代码

Python 代码

相关推荐

评论

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