随笔-14  评论-21  文章-0  trackbacks-0
http://poj.openjudge.cn/practice/1015/ 



设第
k首歌是一定要玩的,则其它歌平均积分为

 

P看作一个置换,设k在置换P下所在循环长度为l,即。考虑P所在的循环,一共有情况,此时P限制在剩余的n-l首歌上也是一个置换,一共有种情况。所以k在置换P下所在循环长度为l的情况个数为。容易看出,此时的期望得分为

 

因此,总期望得分为

#include <iostream>
#include 
<cstdlib>
#include 
<cstdio>
#include 
<algorithm>

using namespace std;

int v[50];

int main(void)
{
    
int u,n,i;
    
long long res;
    scanf(
"%d",&u);
    
while(u--)
    
{
        scanf(
"%d",&n);
        res
=0;
        
for(i=0;i<n;++i)
        
{
            scanf(
"%d",v+i);
            res
+=v[i];
        }

        sort(v,v
+n);
        res
+=v[n-2];
        printf(
"%lld",res>>1);
        
if (res&1)
             puts(
".500000");
        
else puts(".000000");
    }

    
return 0;
}

posted on 2011-05-05 15:04 zxb 阅读(288) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理