Java教程

给定数列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有序的最少操作步数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!