信息
- ID
- 3
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 12
- 已通过
- 4
- 上传者
整个比赛结构是一个满二叉树。要保证进入前三名,至少要打入四强。因为进入半决赛后,即使输掉一场,还可以在铜牌争夺战中获第三。保证自己所在半区没人比自己强即可。
你可以完全控制对阵表,因此只需保证自己所在的半区没有比你更强的选手即可。也就是说,只要你在初始分区中排到的所有选手都不强于你,你就能稳定进入四强。
因此,你的实力只需高于全体选手中一半的人。 设所有其他选手的能力值排序后为:a1≤a2≤……≤a2n−1。
那么你至少需要的能力值为:ans=a2n−1+1。
即超过第 2n−1 强的能力值即可保证进四强。
时间复杂度:o(2nlog2n)。