[关闭]
@rihkddd 2014-09-23T01:02:21.000000Z 字数 1786 阅读 2864

HDU 5035 Delivery 题解

题解 数学 概率 期望


题目大意:

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

解析:

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

f(xλ)={λeλx0,x0,,x<0.

概率分布函数为:
F(xλ)={1eλx0,x0,,x<0.

指数分布具有“无记忆性”,如果一个随机变量呈指数分布,它的条件概率遵循:
P(T>s+t|T>t)=P(T>s)for all s,t0.

然后分析该题目,利用指数分布的无记忆性可以知道,如t0时刻,第i个职员第一个服务完当前客户,那么接着就会服务Matt,然后服务完Matt。这个过程时间的期望就是我们要求的结果。
因此我们要求的就是:
i=1N+0(E(Xi)+x)λieλiji(+xf(x:λj)dx)dx

解释下上面长长的式子:
i个职员t时刻接待Matt的概率为λieλi(此时第i个结束时间为t的概率),乘上ji+xf(x:λj)dx(其它职员结束时间大于t的概率));而这种情况下的时间为(E(Xi)+t)
t可以从0一直取到+,把所有的职员按照上面的情况分析一边,就有了上面的那个式子了。由于指数分布的无记忆性,可以知道题目中给的已服务时间实际上是没有用的……
剩下的就是一些化简计算了,
k=1N+0(E(Xi)+x)λieλiji(+xf(x:λj)dx)dx=k=1N+0(E(Xi)+x)λieλijieλjdx=k=1N+0(E(Xi)+x)λieNi=1λidx=k=1N(1Ni=1λi+λi(Ni=1λi)2)=N+1Ni=1λi

有了这个公式代码应该是不难写,不过要注意这题数据比较多,cin或许或TLE~

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注