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 ;
 }