LightOJ - 1027 Dangerous Maze 期望

你在迷宫中;开始时在你面前看到n扇门。你可以选择你喜欢的任何门。所有门的选择门的概率是相等的。

如果您选择第i个门，它可以让您回到您在xi（xi小于0）分钟内开始的相同位置，也可以在xi（xi大于0）分钟后将您带出迷宫

第一行输入t，代表t个样例，第二行输入一个n，代表这个样例有多少扇门，第三行输入n个数字，如果是正数，那么在经过xi的时间后

你可以离开迷宫，如果xi是负数，那么在|xi|的时间后你又会会到原点，问你离开迷宫的期望是多少。

假设我们离开迷宫的期望是E，如果我们选择xi为正数的门，则只需要花费xi的时间就离开了，如果我们选择xi为负数的门，我们在花费

|xi|的时间后又会到了原点，那么在假设期望E已经知道的情况下，我们从这个点离开迷宫的期望为E，则总时间为|xi|+E，

所以如果有m扇xi为负数的门，则有n-m扇xi为正数的门,那我们先把n个门的绝对值的和时间算出来，

sum=(abs(x1)+abs(x2)+...+abs(xn));所以time=sum+m*E;

那么time/n=E;然后把E全部放在等号一边：E=sum/(n-m),如果n==m则不可能出迷宫，输出inf

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,k,t,sum;

int gcd(int a,int b)

{

    if(!b)

    return a;

    return gcd(b,a%b);

}

int main()

{

    cin>>t;

    int count=;

    while(t--)

    {

        cin>>n;

        sum=m=;

        for(int i=;i<=n;i++)

        {

            cin>>k;

            if(k<)

            m++;

            sum+=abs(k);

        }

        cout<<"Case"<<" "<<++count<<": ";

        if(n==m)

        cout<<"inf"<<endl;

        else

        {

            n=n-m;

            int s=gcd(sum,n);

            sum/=s;

            n/=s;

            cout<<sum<<'/'<<n<<endl;

        }

    }

    return ;

 }

巴特西

LightOJ - 1027 Dangerous Maze 期望

最新文章

热门文章