everybody,求天诛4雷扇魂技,拜托!

将一天分为 n 个小时所以有 n 个时區(当第一个时区的时间为1时,第 i 个时区则为 i 时)现在要举办一场比赛(比赛的时间为 1 个小时)给你每个时区参赛的人数  a ,和一个时间段 s~f当地时间不小于 s 且小于 f 的时间可以参加比赛。求参赛人数最多时最小的开始时间(第一个时区的时间) 

一共可以有 m=f-s 个时区的人可以參加比赛。

在这个问题中需要定义一个“标准时间”(Standard Time),之后将所有的“本地时间”折算成“标准时间”

可以假设一个虚拟的0时区,将这个时区的时间定义为“标准时间”于是:当0时区的“本地时间”(即“标准时间”)为0时,i 时区的“本地时间”为 i

设赛事开始嘚“标准时间”为x,于是:若 i 时区参赛则有:

于是,参赛时区 区间为[s-xf-x-1]或[s-x,f-x)。只需枚举x并将对应区间中的参赛人数求和,即可寻找参赛囚数的最大值可以考虑前缀和,或者滑动窗口(注:窗口的滑动方向应该是循环向左的)


  

参考资料

 

随机推荐