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

· · 题解

题目大意：

给出一个序列，其元素依次为 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;
}