[CH0601]Genius ACM[倍增]

题面(CH暂时无法访问)

为了划分出最少的段数, 我们必须使每一段在校验值不超过T的前提下尽可能长. 以一段的开头为L, 结尾为R, 于是问题就转化成了已知L的情况下怎样找到一个尽量大的R使校验值不超过T.

为了求出校验值, 要对序列进行排序. 因为序列越长校验值一定越大, 我们可以考虑在区间L~N上二分, 但是T很小时, R可变化的范围其实比较小, 而二分检查的是整个L~N一大段, 浪费了时间.

正解是从L开始倍增, 因为这样可以保证在$latex O(\log (R-L))$的时间内找到最大的R, 而二分需要$latex O(\log (N-L))$的时间. 前者显然更优.

在排序上也有一点优化: 若每次判定时都把要判定的区间快排一次, 时间复杂度是$latex O(N\log^2 N)$. 而每次只快排倍增多出来的区间那一部分, 再与之前的排过序的部分合并, 时间复杂度降低到$latex O(N\log N)$.


赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址