Description

给一个1~n的排列p[i],Jeff先手可以交换任意两个相邻元素,而Furik会有0.5的几率把任意满足p[i] < p[i+1]的p[i]和p[i+1]交换,有0.5的几率把任意满足p[i] > p[i+1]的p[i]和p[i+1]交换,问将整个序列变成升序所需的最小期望步数

Input

第一行一整数n表示序列长度,之后一个1~n的排列p[i] (1<=n<=3000)

Output

输出把整个序列变成升序所需的最小期望步数

Sample Input

5
3 5 2 4 1

Sample Output

13.000000

Solution

考虑E[i](i为逆序对个数)的最小期望步数,则E[0]=0,E[1]=1;那么每一次Jeff肯定是交换使逆序对减少一个而Furik则有50%减少一个50%增加一个,故$E[i]=1/2*(E[i-2]+1)+1/2*(E[i-1+1]+1)$;化简得$E[i]=E[i-2]+4$;

故模拟归并排序求一次逆序对个数便可实现。

Code

#include<bits/stdc++.h>
#define maxn 3005
using namespace std;
int n,a[maxn],t[maxn];
int msort(int l,int r){
    if(l==r) return 0;
    
    int m=l+r>>1;
    int t1=msort(l,m);
    int t2=msort(m+1,r);
    
    int t3=0;
    int i=l,j=m+1,k=l;
    while(i<=m&&j<=r){
        if(a[i]>a[j]){
            t3+=m-i+1;
            t[k++]=a[j++];
        }
        else{
            t[k++]=a[i++];//本来就应该小于 
        }
    }
    while(i<=m) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    
    for(int p=l;p<=r;p++) a[p]=t[p];//调整
    return t1+t2+t3; 
}
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int nd=msort(1,n);
    if(nd&1){
        printf("%lf",(double)(2*nd-1));
    }
    else printf("%lf",(double)2*nd);
}
int main(){
    init();
    
    return 0;
}
Last modification:February 15th, 2019 at 09:26 pm