求助各位dalao

2017-01-07 19:11:58 By Sky_miner

遇到了一个问题，向各位dalao求助.

给定一个长为n的序列(数字大小两两不同),老师想把这个序列排序。
他会掷一枚均匀硬币.如果正面朝上,他就会选择一对满足左边的数比右边大的相邻元素进行交换,否则选中一对满足左边的数比右边小的相邻元素进行交换.
如果无法进行交换,他就再扔一次硬币.如果序列按递增顺序排好序,那么操作结束.问期望的操作次数
(n <= 3000)

这道题我写出了一个算法，但是发现算出来的所有的答案都是整数。是不是这个题的性质就决定了答案一定是整数？

本苣表示不理解，希望各位dalao能够解答一下。感激不尽。。。

AntiLeaf

你写暴力了吗......

2017-01-08 10:06:36
回复

WrongAnswer

设序列的逆序数为 $m$，则掷硬币的次数期望值应该是 $m[n(n-1)-m+1]$，如果我没推错的话。（推错别怪我）

2017-01-08 15:18:29
回复

Sky_miner

#include<cstdio> const int maxn=3010*3010; int a[maxn]; double k[maxn],b[maxn]; int main(){ //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int n;scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); } int cnt = 0; for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(a[i]>a[j])cnt++; } } int lim=n*(n-1)/2; k[1]=1;b[1]=0;//f[i]=k[i]*f[1]+b[i] k[2]=2;b[2]=-2; for(int i=3;i<=lim;++i){ k[i]=2*k[i-1]-k[i-2];b[i]=2*b[i-1]-b[i-2]-2; } double f1=(b[lim-1]-b[lim]+2)/(k[lim]-k[lim-1]); //printf("%.7f\n",f1); printf("%.7f\n",k[cnt]*f1+b[cnt]); getchar();getchar(); return 0; } 这个是我的程序,设F[i]为还剩i个逆序对的时候期望的掷硬币次数,则F[0]=0,F[1]=1+0.5F[0]+0.5F[2]....F[n*(n-1)]=2+0.5F[n*(n-1)-1],然后可以O(n*(n-1))的时间解这些方程.非常的naive...

2017-01-08 15:50:49
回复

Sengxian

[http://codeforces.com/problemset/problem/351/B](http://codeforces.com/problemset/problem/351/B)。

2017-01-15 17:06:57
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Sky_miner的博客

博客

求助各位dalao

评论

发表评论