【POJ 3614 Sunscreen】貪心 優先級隊列

題目連結：http://poj.org/problem?id=3614

題意：C頭牛去曬太陽，每頭牛有自己所限定的spf安全範圍[min, max]；有L瓶防曬液，每瓶有自己的spf值和容量（能供幾頭牛用）。

求這L瓶防曬液最多能讓多少頭牛安全地曬太陽。

思路：貪心政策，按spf從小到大或從大到小的順序取出防曬液，供給盡可能多的剩餘的牛。

具體如何判斷目前這瓶防曬液最多能供給幾頭牛呢？

以spf從小到大排序所有防曬液為例，可以維護一個小頂堆，每取出一瓶防曬液l，就把剩餘的所有min值低于l.spf的牛的max值放入堆中。

接下來在l的容量尚未耗盡時，反複彈出并比較堆頂值與l.spf，若大于l.spf，則 l 消耗1機關的容量供給這頭牛，計數值加1；否則這頭牛不能被任何防曬液供給（目前spf已經是剩餘的最小值，後續不會有更小的）。反複取堆頂元素直至容量耗盡或堆變空。各瓶防曬液的計數值的總和即為答案。

首先需要将防曬液按spf值從小大到排序（O(LlogL)），以及将牛按min值從小到大排序(O(ClogC))；然後外層循環對L瓶防曬液進行一遍掃描(O(L))，内層循環每頭牛的max必然入堆一次、彈出一次(Ω(C))，是以總的複雜度為O(LlogL + CLogC + LC)。

自己實作的堆，時間上總是比STL的priority_queue慢一些，不過空間更少。