标签:堆

OI

[POJ2431]Expedition[贪心,堆]

cgazn阅读(112)评论(0)赞(0)

题面 一开始想到一个错误策略: 每次在当前油量能走到的范围内找油最多的加油站…后面发现有可能会要在范围内多次加油才可能走到终点, 需要根据油量从大到小依次选择加油站, 于是容易想到用一个大根堆来维护所有可以走到的油站, 直到不能...

OI

[POJ3190]Stall Reservations[贪心]

cgazn阅读(83)评论(0)赞(0)

题面 首先要把牛按照开始时间升序排序, 不然安排一头牛时这头牛开始时间之前我们都管不了了, 可能造成浪费一段正好可以安排后面一头开始时间更早的牛的空档. 而按开始时间排序后就能线性的安排每头牛, 保证安排到每一头牛时这头牛的开始时间之前已经...

OI

[POJ3784]Running Median[堆]

cgazn阅读(99)评论(0)赞(1)

题面 题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数). 设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分. 资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分...