EllysRoomAssignmentsDiv1

作者：闵梓轩

关键词：字符串，排序，期望

题目简述

• 一场topcoder的比赛中有若干个选手，每个选手都有自己的rating，如果n是20的倍数，他们将 会被分派到$\frac{n}{20}$个房间中，否则房间数为$\left[\frac{n}{20}\right] +1$。每次分配时会将与房间数相等的当前rating最高的几位选手随机分配到每个房间中，直到剩下的人数少于房间数，此时将这些选手随机分配到这些房间中，每个房间最多分配$1$名这类选手。
• Elly是一名参加这场比赛的选手，以字符串数组的形式给出这场比赛所有参赛选手的rating列表，请帮她计算出她所在的房间的所有选手期望的rating平均值。
• 数据保证字符串数组大小不超过50，每个字符串长度不超过50，每个选手的rating值都是$1200$到$3923$之间的整数，且任意两名选手的rating值都不相同。

算法一

首先我们将字符串数组转换成整数数组（C++中可以使用string重载的+运算符直接进行拼接），记录下Elly的分数$sc$然后排序，计算出房间总数$r$，每个房间的人数$p$以及最后剩下的人数$k$之后进行模拟： 每次分配时，如果Elly在这组中，此次那么分配到Elly房间的选手的期望rating就是Elly自己的rating，否则为这组所有选手rating的平均值。 计算出Elly所在房间期望rating和$sum$后，剩下的选手中如果有Elly，则答案为$\frac{sum+Elly}{r+1}$。否则这些选手中有人被分配到Elly房间的概率为$\frac{k}{r}$，记这些选手的平均rating为$a$，则答案为$\frac{k}{r}*\frac{sum+a}{r+1} + \left(1 - \frac{k}{r} \right)*\frac{sum}{r}$ 如果记选手总数为$n$，那么显然$n\leq\frac{50*50}{4+1}=500$，上述算法中$n =O\left(n\log{n}\right)$，可以通过此题。