题解 CF351B

CF351B

Description

两个人 A，B，一个长为 $n$ 的序列，A 每次选两个相邻元素交换，B 有相等的概率把任意满足 $p_i<p_{i+1}$ 的 $p_i$ 和 $p_{i+1}$ 或 $p_{i}>p_{i+1}$ 的 $p_{i}$ 和 $p_{i+1}$ 交换。

求将序列变成升序的最小值期望步数。

Solution

每一次 A 肯定是交换一个逆序对，而 B 每次有 $50\%$ 的概率减少一个逆序对，有 $50\%$ 增加一个逆序对，设 $f_i$ 表示 $i$ 个逆序对时的最小期望步数，则转移为 $f_i=\frac{1}{2}(f_{(i-1)-1}+2)+\frac{1}{2}(f_{(i-1)+1}+2)$

化简一下：

$f_i=f_{i-2}+4$

易知 $f_0=0,f_1=1$ 。

然后我们发现当 $ f_i$ 是偶数的时候，$f_i=f_{\frac{i}{2}}+4=(f_{\frac{i}{4}}+4)+4=\dots=f_0+4\times\frac{i}{2}=2i$

当 $f_i$ 是奇数的时候，$f_i=f_{\frac{i}{2}}+4=(f_{\frac{i}{4}}+4)+4=\dots=f_1+4\times(\lfloor\frac{i}{2}\rfloor-1)=2i-1$

然后求一次逆序对个数，根据奇偶性判断就行了。

Code

/*
* @Author: smyslenny
* @Date:    2021.09.04
* @Title:   CF351B Jeff and Furik
* @Main idea:求逆序对个数，判断奇偶性，Ans=2*odd-1 || 2*even 
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>

#define ll long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)
#define lowbit(x) (x)&(-x)

using namespace std;
const int mod=998244353;
const int M=3e3+5;
int n,Ans;
int read()
{
	int x=0,y=1;
	char c=getchar();
	while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
	while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
	return y?x:-x;
}

struct node{
	int val,id;
}sz[M];

bool cmp(const node &a,const node &b)
{
	return a.val<b.val;
}

int sum[M];
void add(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
		sum[i]+=k;
}

int query(int x)
{
	int cnt=0;
	for(int i=x;i;i-=lowbit(i))
		cnt+=sum[i];
	return cnt;
}

int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		sz[i].val=read(),sz[i].id=i;
	sort(sz+1,sz+1+n,cmp);
	for(int i=1;i<=n;i++)
		add(sz[i].id,1),Ans+=(i-query(sz[i].id));
	if(Ans&1)
		printf("%lf\n",(double)2*Ans-1);
	else 
		printf("%lf\n",(double)2*Ans); 
	return 0;
}