自动搬运

查看原文

来自洛谷，原作者为

	wenqinghua1001 ZYX0716 是指以(0,0,0)为原点，Z轴是7，Y轴是1，X轴是6的点||离线||估值：100+51+71+46+30=298||欢迎互关，私信，可小号双关 ||不开long long见祖宗，开了long long爆内存||喜欢出题的六年级蒟蒻

搬运于2025-08-24 23:13:26，当前版本为作者最后更新于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)