当前位置：首页 -> 基础 -> c++编程基础

POJ 3190 Stall Reservations-奶牛分栏（区间贪心，优先队列）(二)

2015-01-27 10:00:54 · 作者: · 浏览: 44
标签: POJ 3190 Stall Reservations- 奶牛 区间 贪心 优先 队列
，每次更新时，查找set，并且从中删除元素。放入元素复杂度，log(1) + log(2) ...+log(n) = log(n!)。遍历复杂度，我们假设最坏情况，每次遍历删除一个元素： 2log(n!)
  • 算法1解法2 元素存入数组中，每次遍历数组，标志已经删除的元素。排序：nlog(n) 。遍历，同样是最坏情况，每次前进一个元素（二分查找）：log(n) + log(n-1) + log(1) = log(n!)
  • 算法2解法1 维护一个最小堆，每次更新最小堆。排序： nlog(n) 。最小堆维护，最坏情况，每次都无法更新最小堆：log(n) + log(n-1) + log(1) = log(n!)