LightOJ1027 A Dangerous Maze（期望）

题目大概说你正在起点，面前有$n$个门，每个门有一个数字$x$，正数表示开这个门$x$分钟后会出去，负数表示开这个门$-x$分钟后会回到起点。选择门的概率是一样的且每次选择互不影响。问出去的时间期望是多少。

$d[0]$表示从起点出发出去的期望，$d[i]（1\leqslant i\leqslant n）$表示选择第i个门出去的期望；

不妨设$1\dots j$的门是正数，$j+1\dots n$的门是负数，那么：

$$d[i]=x[i]（1\leqslant i\leqslant j）$$

$$d[i]=x[i]+d[0]（j+1\leqslant i\leqslant n）$$

由于每个门被选择的概率均等，那么：

$$d[0]=\frac{\sum_{i=1}^{j}x[i]+\sum_{i=j+1}^{n}(x[i]+d[0])}{n}$$

$$d[0]=\frac{\sum_{i=1}^{n}x[i]}{n-j}$$

这样计算出$d[0]$就是要的结果了。队友教的。

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int gcd(int a,int b){

     if(b==) return a;

     return gcd(b,a%b);

 }

 int main(){

     int t,n,a;

     scanf("%d",&t);

     for(int cse=; cse<=t; ++cse){

         scanf("%d",&n);

         int tot=,cnt=;

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

             scanf("%d",&a);

             if(a<) tot-=a,++cnt;

             else tot+=a;

         }

         int x=tot,y=n-cnt;

         if(y==) printf("Case %d: inf\n",cse);

         else printf("Case %d: %d/%d\n",cse,x/gcd(x,y),y/gcd(x,y));

     }

     return ;

 }

巴特西

LightOJ1027 A Dangerous Maze（期望）

最新文章

热门文章