给定数列P，求通过交换数列P中的元素使数列P有序的最少操作步数

本文主要是介绍给定数列P，求通过交换数列P中的元素使数列P有序的最少操作步数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考虑使序列P最终升序
1.若只能交换相邻元素，由于每一次有效交换，都会使序列的逆序对数目减少1，故最小交换次数即为序列P的逆序对数目。可用树状数组求解逆序对数目。

2.若可以任意交换序列中的元素，可贪心的考虑。每一次有效交换都至少使一个数到达其最终所在的位置。故遍历i从1到n，如果i在其最终的位置，则跳过，否则把i与a[i]交换，并维护一系列信息。

#include<cstdio>
using namespace std;
int val[50010],pos[50010];
//pos[i]表示第i个位置的数，val[i]表示数字i在val[i]位置 
int n;
inline void swap(int &x,int &y){
	int t=x;
	x=y;
	y=t;
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data1.out","w",stdout);
	scanf("%d",&n);
	for(register int i=1;i<=n;i++){
		scanf("%d",&pos[i]);
		val[pos[i]]=i;
	}
	int ans=0;
	for(register int i=1;i<=n;i++){
		if(i!=val[i]){
			int x=pos[i];
			swap(pos[i],pos[val[i]]);
			swap(val[i],val[x]);
			ans++; 
		}
	}
	printf("%d\n",ans);
	return 0;
} 

每一次交换,val[i]与val[pos[i]]会交换，且pos[i]与pos[val[i]]会交换。
val数组的作用：判断i是否在其最终的位置。
pos数组的作用：快速找到应与i交换位置的数。
算法复杂度：O(n)

若要求数组降序，其实只需把判断条件改为：n-i+1==val[i]。

这篇关于给定数列P，求通过交换数列P中的元素使数列P有序的最少操作步数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！