CF351B Solution

题解

设逆序对个数为(cnt)，如果只有Jeff进行游戏，只需执行(cnt)次操作（每次操作减少一个逆序对）。考虑Furik，他有(frac{1}{2})的概率增加一个逆序对，也就是增加(2)次操作；剩下的一半概率减少一个逆序对，也就是不增加操作数。所以他每次操作对期望的贡献是(2 imes frac{1}{2}+0 imesfrac{1}{2}=1)。因此答案(=cnt+)Fruik的操作数(=2cdot cnt-cnt\%2)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int p[N];
inline int read()
{
	int s=0,w=1; char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int main()
{
	int n=read(),cnt=0;
	for(int i=1;i<=n;i++) p[i]=read();
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(p[i]>p[j]) cnt++;
	printf("%.6lf",2.0*cnt-cnt%2);
	return 0;
}