要使团队得分最大,既要团队的速度和尽量大,又要最低效率的人的效率尽量大。相比于思考一堆人的速度和,观察一个人的效率更方便。于是我们很容易想到突破点,那就是如果一个人是团队中效率最低的,那么这个团队该如何组建?很显然我们在所有效率比他高的人里面,取speed最大的k个人。
所以我们按照把人按照效率从高到低排列。对于任何一个人而言,如果让它做团队里效率最低的,那么在他之前的那些人自然都能入选团队。我们只需要用一个优先队列,在当前所有人中保留速度最大的k个即可。
注意,我们不会将PQ里面的k个元素直接相加来计算团队的速度和,因为这样当k很大的时候时间复杂度很高。我们维护一个小顶堆的优先队列,每加入一个人的速度之后,淘汰里面速度最低的一个,这样用o(1)的时间就可以来维护团队的速度和。