LightOj 1027 数学期望

一个迷宫有n扇门，走第i扇门时间为 xi $x_i$，若 xi $x_i$为正，则走出迷宫，若 xi $x_i$为负，则回到原来位置并忘记已走过的门。问走出迷宫的时间期望，若不能走出迷宫输出inf，否则以分数形式输出 p/q $p/q$。

---

【数据范围】
T(≤100) $T(\le 100)$组数据， 1≤n≤100,1≤abs(xi)≤10000 $1\le n\le 100,1\le abs(x_i)\le 10000$。

---

【分析】
首先对于题目给定的如下样例应该如何推得答案为 18/1 $18/1$,

3
3 -6 -9

设定期望为d，即 d=13×3+13×(6+d)+13×(9+d) $d=\frac{1}{3}\times 3+\frac{1}{3}\times (6+d)+\frac{1}{3}\times (9+d)$；
所以推得 13×d=1+2+3 $\frac{1}{3}\times d=1+2+3$，故得最后 d=18 $d=18$；
同样的当有n个数时，我们假定有a个为正数，b个负数，
就有 d=1n×∑(正数)+1n×(∑(负数)+b×d) $d=\frac{1}{n}\times \sum (正数)+\frac{1}{n}\times (\sum (负数)+b\times d)$，从而 an×d=1n×∑ni=1xi $\frac{a}{n}\times d=\frac{1}{n}\times \underset{i=1}{\overset{n}{\sum }}{x}_i$，
最后 d=∑ni=1xia $d=\frac{\underset{i=1}{\overset{n}{\sum }}{x}_i}{a}$,当然，当 a=0 $a=0$时那就输出 inf $inf$。

---

【代码】

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int res, T, n;
int tot;
int main() {
    scanf("%d", &T);
    while(T--) {
        printf("Case %d: ", ++tot);
        scanf("%d", &n);
        int x = 0;
        res = 0;
        for(int i = 1; i <= n; i++) {
            int a;
            scanf("%d", &a);
            if(a > 0)x++;
            res += abs(a);
        }
        if(x == 0)printf("inf\n");
        else {
            int tmp = __gcd(res, x);
            printf("%d/%d\n", res / tmp, x / tmp);
        }
    }
    return 0;
}