Light oj 1027 A Dangerous Maze ----计算期望

有n扇门，每次你可以选择其中一扇。xi为负值的门带你abs(xi)后又回到原点。xi为正值

的门则带你离开迷宫。每次你都没有经验没有记忆。选择每扇门的概率相等。求走出迷宫

的时间期望值。

算法：

设为正值的门的数量为n1，总共有n扇门。

走一次就出来的概率是n1/n，走出来的期望次数是n/n1.

走一次需要的平均时间为sum(ti)/n (1<=i<=n)

则走出来的时间期望是 sum(ti)/n *(n/n1) =sum(ti)/n1 .

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    int T,cas=1,sum,cnt,t,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        sum=0,cnt=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&t);
            if(t>0)
                sum+=t;
            else
            {
                sum-=t;
                cnt++;
            }
        }
        int n1=n-cnt;
        if(n1==0)
        {
            printf("Case %d: inf\n",cas++);
            continue;
        }
        int tmp=gcd(sum,n1);
        printf("Case %d: %d/%d\n",cas++,sum/tmp,n1/tmp);
    }
    return 0;
}

Light oj 1027 A Dangerous Maze ----计算期望

原文：http://blog.csdn.net/u012841845/article/details/19162103