题意:
两人游戏, J先走.
给出一个1~n的排列, J选择一对相邻数[题意!!~囧], 交换.
F接着走, 扔一硬币, 若正面朝上, 随机选择一对降序排列的相邻数, 交换. 若反面朝上, 随机选择一对升序排列的相邻数, 交换.
当数列成为严格升序的时候游戏结束.
求让游戏尽早结束的情况下, 移动次数的期望.
思路:
首先分析游戏结束的方法: 由于是排列, 严格升序就是1~n. J的话..直接按顺序将较小的数交换到目标位置即可. F的话…比较麻烦, 有两种可能, 每种可能都是随机的…..就会破坏J的结果….
这样的话就要进死胡同了….
需要深刻理解”期望”…就是概率相消会认为是事实… 分析第二个人, 他一半是随机选择升序变降序, 一半是随机选择降序变升序…YY一下, 可以认为F啥也没干…
那就直接求J走的步数, F只是起到填充的作用…注意F必须走偶数步使得他自己的作用可以中和掉.
下面就是模拟一下样例: 对于某个数, 它移动的次数就是在它前面比他大的数的个数[逆序数], 在他前面比他小的数不需要被它超越. 而他本身的移动将排列分成三个区间, 前面没涉及的部分, 逆序数显然没影响, 中间跨过的部分, 它的到来并不会使这些数的逆序数增加, 更不会减少, 他后面的部分, 显然也是没有影响… 因此, 只要计算整个排列的逆序数的个数即可.
线段树可以算逆序数…但是好麻烦吧…
归并排序求逆序数:
冒泡也可以求逆序数..就相当于是这个游戏的模拟解法..O(n^2), 反而是冒泡为什么可以求出逆序数可以由此题的分析过程得出…
归并的话, O(nlogn)…
基本操作是将左右两个有序数组合并. 左右两个数组内部的排序对逆序数的改变只影响其内部, 所以可以分层累加.
合并时, 从左边来的数的逆序数都不变, 每从右边来一个数, 它的逆序数就增加”左边剩余数”的个数. 所有的都累加一下就可以了.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 3005;
int p[MAXN],n,cnt,t[MAXN];
void mrg(int l, int r)
{
int mid = (l + r) >> 1;
int i = l, j = mid + 1, k = 0;
while(i<=mid && j<=r)
if(p[i]<p[j]) t[k++] = p[i++];
else
{
t[k++] = p[j++];
cnt += mid - i + 1;
}
if(i>mid)
while(j<=r) t[k++] = p[j++];
else
while(i<=mid) t[k++] = p[i++];
for(i=0;i<k;i++)
p[l+i] = t[i];
}
void srt(int l, int r)
{
if(l<r)
{
int mid = (l + r) >> 1;
srt(l, mid);
srt(mid+1,r);
mrg(l,r);
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",p+i);
srt(0, n-1);
printf("%.6lf\n",(double)((cnt&1)?((cnt<<1)-1):cnt<<1));
}
