HDU 5035 Delivery 题解

题解 数学 概率 期望

---

题目大意：

Matt去发快递，快递点有N个职员，职员处理一个客户的时间服从指数分布：$f(t) = \lambda e^{-\lambda t}$,其中的参数$\lambda$为职员的效率，现在给出每个职员的效率，同时给了一个场景：现在每个职员都有且只有客户在服务中，此人还从信息牌得知了每个职员已经为当前客户服务了c时间，题目中也给出了，一旦有客户被服务完毕，则这个人就立刻去接受服务。问在此场景下，这个人发快递需要的时间的期望是多少？

解析：

首先几何分布的一些性质：
一个几何分布的概率密度函数是：

$$f(x\: \lambda )= \begin{cases} \lambda e^{ -\lambda x } & ,\; x\ge 0, \\ 0 & ,\; x<0. \end{cases}$$
概率分布函数为：
$$F(x \: \lambda )= \begin{cases} 1-e^{-\lambda x}&,\; x \ge 0, \\ 0 &,\; x < 0. \end{cases}$$
指数分布具有“无记忆性”，如果一个随机变量呈指数分布，它的条件概率遵循：
$$P(T > s + t\; |\; T > t) = P(T > s) \;\; \hbox{for all}\ s, t \ge 0.$$
然后分析该题目，利用指数分布的无记忆性可以知道，如$t_0$时刻,第$i$个职员第一个服务完当前客户，那么接着就会服务Matt，然后服务完Matt。这个过程时间的期望就是我们要求的结果。
因此我们要求的就是：
$$\sum_{i=1 }^N{\int _0 ^ {+\infty}(E(X_i)+x) \lambda _ie^{-\lambda_i}\prod_{j\neq i}( \int_x ^{+\infty}f(x:\lambda_j) dx)d x}$$
解释下上面长长的式子：
第$i$个职员t时刻接待Matt的概率为$\lambda _ie^{-\lambda_i}$(此时第i个结束时间为t的概率)，乘上$\prod _{j\neq i}\int_x ^{+\infty}f(x:\lambda_j) dx$（其它职员结束时间大于t的概率))；而这种情况下的时间为$(E(X_i)+t)$
t可以从$0$一直取到$+\infty$，把所有的职员按照上面的情况分析一边，就有了上面的那个式子了。由于指数分布的无记忆性，可以知道题目中给的已服务时间实际上是没有用的……
剩下的就是一些化简计算了，
$$\begin{eqnarray} \sum_{k=1 }^N {\int _0 ^ {+\infty}(E(X_i)+x) \lambda _ie^{-\lambda_i}\prod_{j\neq i}( \int_x ^{+\infty}f(x:\lambda_j) dx)d x}\\ =\sum_{k=1 }^N{\int _0 ^ {+\infty}(E(X_i)+x) \lambda _ie^{-\lambda_i}\prod_{j\neq i}e^{\lambda _j}}dx\\ =\sum_{k=1 }^N{\int _0 ^ {+\infty}(E(X_i)+x) \lambda _ie^{-\sum _{i=1}^N\lambda _i}}dx\\ =\sum_{k=1 }^N({\frac{1}{\sum _{i=1}^N\lambda _i}+\frac{\lambda _i}{{(\sum _{i=1}^N\lambda _i})^2})}\\ =\frac{N+1}{\sum _{i=1}^N\lambda _i} \end{eqnarray}$$
有了这个公式代码应该是不难写，不过要注意这题数据比较多，cin或许或TLE～