危险的迷宫
↑ 题目链接
题目
你在一个迷宫的起点，你面前有 \(n\) 扇门，编号 \(1∼n\) 。
其中，第 \(i\) 扇门的权值为 \(x_i\) ，如果 \(x_i\) 为正，表示进入第 \(i\) 扇门可以让你在 \(x_i\) 分钟后逃离迷宫，如果 \(x_i\) 为负，则表示进入第 \(i\) 扇门会使你浪费 \(|x_i|\) 分钟后再次回到起点。
每当你位于起点时，你都会随机选择一扇门进入，每扇门被选中的概率均相同。
请你计算，你逃离迷宫的期望时间。
输入格式
第一行包含整数 \(T\) ，表示共有 \(T\) 组测试数据。
每组数据第一行是空行。
第二行包含整数 \(n\)。
第三行包含 \(x_1,x_2,…,x_n\)
输出格式
每组数据输出一行结果，格式为 Case x: y，其中 \(x\) 为组别编号（从 1 开始），\(y\) 期望时间，以 \(p/q\) 的格式输出，其中 \(p\) 为结果的分子，\(q\) 为结果的分母，\(p,q\) 应该互质。如果无法走出迷宫，则 y 应该为 inf。
数据范围
\(1≤T≤100,1≤n≤100,1≤|x_i|≤10000\)
输入样例：
3
1
1
2
-10 -3
3
3 -6 -9
输出样例：
Case 1: 1/1
Case 2: inf
Case 3: 18/1
思路
设总的期望值为 \(E\) ，权值为正的期望值 \(E_1= \frac{\sum \limits_{x_i>0}x_i}{n} = \frac{sum_1}{n}\) ，权值为负的期望值 \(E_2= \frac{\sum \limits_{x_i<0}|x_i+E|}{n}=\frac{sum_2+cnt_{x_i<0}*E}{n}\)，
\[\begin{align} E &=E_1+E_2\\ &=\frac{sum_1+sum_2+cnt_{x_i<0}*E}{n}\\ \end{align} \]整理可得 \(E =\frac{sum_1+sum_2}{n-cnt_{x_i<0}}\)
代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N][N];
int a[N];
int main()
{
int T;
cin>>T;
for(int Case=1;Case<=T;Case++)
{
int n;
cin>>n;
int p=0,q=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(x<0)q++;
p+=abs(x);
}
printf("Case %d: ",Case);
if(q==n)puts("inf");
else
{
q=n-q;
int d=__gcd(p,q);
printf("%d/%d\n",p/d,q/d);
}
}
return 0;
}