自动搬运

查看原文

来自洛谷，原作者为

	ZYX0716 **

搬运于2025-08-24 23:12:54，当前版本为作者最后更新于2025-04-29 21:12:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：

给出一个序列，其元素依次为 $1,2,3,\cdots,51$。每次随机交换两对数，请你求出逆序对的数量的期望值。

由于题目中未给出逆序对的定义，在这里强调一下：逆序对就是数组序列中 $a[i]>a[j]$ 且 $i<j$ 的有序对。

思路：

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

暴力求答案：

#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：

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