[POJ3190]Stall Reservations[贪心]

题面

首先要把牛按照开始时间升序排序, 不然安排一头牛时这头牛开始时间之前我们都管不了了, 可能造成浪费一段正好可以安排后面一头开始时间更早的牛的空档. 而按开始时间排序后就能线性的安排每头牛, 保证安排到每一头牛时这头牛的开始时间之前已经排满, 只要考虑这头牛结束后的安排. 事实上许多含上界下界的问题都不能同时考虑上下界, 必须先保证一端线性变化, 才好考虑另外一端.

排序之后依次考虑每一头牛. 我们用一个小根堆维护所有牛棚的最后一头牛的结束时间, 看新的一头牛是否能接在最早结束的一个牛棚(堆顶)的后面, 如果能就更新(先pop再push)这个牛棚(堆顶)的结束时间, 不能就直接新增一个牛棚, 把这个新牛棚也push到堆里去.

赞(0)

评论 抢沙发

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