题解：P12122 [蓝桥杯 2024 省 B 第二场] 逆序对期望

题目大意：

给出一个序列，其元素依次为

1,2,3,\cdots,51

。每次随机交换两对数，请你求出逆序对的数量的期望值。

由于题目中未给出逆序对的定义，在这里强调一下：逆序对就是数组序列中

a[i]>a[j]

且

i<j

的有序对。

思路：

因为只需输出答案，因此可以先暴力求出结果。求逆序对的方法我这里用的是归并排序。

暴力求答案：

CPP

#include<bits/stdc++.h>
using namespace std;
int n=51,a[505],b[505];
double ans,s;
void merge(int l1,int r1,int l2,int r2){
	int cnt=0,begin=l1,end=r2;
	while(l1<=r1 && l2<=r2){
		if(a[l1]<=a[l2]){
			b[++cnt]=a[l1++];
		}else{
			b[++cnt]=a[l2++];
			ans+=r1-l1+1;
		}
	}while(l1<=r1){
		b[++cnt]=a[l1++];
	}while(l2<=r2){
		b[++cnt]=a[l2++];
	}for(int i=begin,j=1;i<=end && j<=cnt;i++,j++){
		a[i]=b[j];
	}
	return;
}
void mergesort(int l,int r){
	int mid=(l+r)/2;
	if(l<mid)mergesort(l,mid);
	if(mid+1<r)mergesort(mid+1,r);
	merge(l,mid,mid+1,r);
	return;
}
//merge与mergesort函数是归并模板。
int main(){
	for(int i=1;i<=n;i++){//原数列。
		a[i]=i;
	}for(int i=1;i<=n;i++){//暴力枚举。
		for(int j=i+1;j<=n;j++){
			for(int k=1;k<=n;k++){
				for(int l=k+1;l<=n;l++){
					swap(a[i],a[j]);
					swap(a[k],a[l]);
					mergesort(1,n);
					s++;
				}
			}
		}
	}
	printf("%.2lf",ans/s);//输出答案。
	return 0;
}

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
int main(){
	double ans=65.33;
	printf("%.2lf",ans);
	return 0;
}

题解：P12122 [蓝桥杯 2024 省 B 第二场] 逆序对期望

文章操作

题目大意：

思路：

暴力求答案：

AC Code：

相关推荐

评论

题解：P12122 [蓝桥杯 2024 省 B 第二场] 逆序对期望