Codeforces GYM 2016-2017 NEERC, Moscow Subregional L. Lazy Coordinator

14
May

Codeforces GYM 2016-2017 NEERC, Moscow Subregional L. Lazy Coordinator

训练做gym的时候碰到的一道题,难度不大,过的人挺多,但是我们一直没过,我事后看题解也看了挺久才懂,记录一下。

题面描述
给出N个球放入黑箱和从中摸出的时间,问每个球被摸出所需要的时间期望是多少。

解题思路
首先我们要注意到,被摸出所需要的时间期望=被摸出期望时刻-放入的时间。注意到这点后,我们开始考虑期望的定义下,没有球再将被放入时每个球被摸出的期望时刻的意义,它等于完摸完箱中剩余所有球可能的时刻之和除以箱中球的数量。我们将其推广到更一般的情况,当可能有球会在当前球之后被放入时,我们提前计算那些球的期望时刻,并把它们减去,从而构造为等价于简单情况。
为了达到这个目的,我们从后向前运算,因为必定先碰到摸球事件再碰到放球事件,所以不会在第一次计算时就需要减去,那么之后就可以连续地递推了,时间复杂度为O(n)。

AC代码
https://paste.ubuntu.com/p/Y4zkY753g5/

由于个人水平有限,上述文字可能存在错误,如有问题,欢迎指正和讨论!

添加新评论