题意 : 在n个门前选择一扇门出去, 然后如果第i扇门的 Xi值是正的话,你会花费Xi时间后出去 , 如果Xi是负数的话你会花费-Xi时间后回到老地方,并且忘记了刚才的选择, 选择一扇门的概率是等概的。求出去的期望。
思路 :定义一次选择选择到Xi是整数的概率为P1,选择到负数的概率是P2,然后选择了正数后平均在T1时间后出去, 选择了负数后平均在T2时间后回到原地。接着设出去的期望是Y,那么可以写出一个式子 :Y = P1 * T1 + P2 * (T2 + Y), 这样的话问题就得到了解决, 最后整理下式子就是 : Y = 正数个数的倒数 * ∑abs(Xi) ;
#include <cstdio> #include <cstring> int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } int main(){ int T, n; scanf("%d", &T); for (int cas = 1; cas <= T; cas++){ scanf("%d", &n); int pos = 0, posv = 0, neg = 0, negv = 0; for (int i = 1; i <= n; i++){ int a; scanf("%d", &a); if (a > 0){ pos++; posv += a; }else{ neg++; negv += -a; } } printf("Case %d: ", cas); if (pos == 0){ printf("inf\n"); continue; } int up = posv + negv; int down = n - neg; int t = gcd(up, down); printf("%d/%d\n", up/t, down/t); } return 0; }