HOJ85-毛毛蟲問題

題目：http://hoj.mooo.com/judge/index.php/problem/view/85
(我超愛這題的題目描述，好可愛阿≧ｘ≦)
有N隻(N<=300000)毛毛蟲，想選出儘量多的毛毛蟲放進觀察箱裡並讓它們存活
每隻毛毛蟲有二氧化碳排放量a以及忍受度b
讓觀察箱中平均每隻毛毛蟲收到的二氧化碳都不超過b

程式碼(作法一)：http://codepad.org/UmlGpkiJ
程式碼(作法二)：http://codepad.org/bHNd0B75

[作法一]
「有n個正整數數對，n的總數到10萬級」

實在讓人很難不朝貪心去聯想

所以趕快把毛毛蟲按照排放量排序呢？還是照忍受度排序好呢？

「從n個元素中選定x個元素令他們的平均值最小/最大」

讓人想起了最小平均值環、最優比例生成樹這些通過移項、二分答案解決的題目

二分答案吧！

我首先這麼想，然後開始嘗試證明答案有單調性

即：如果存在n隻毛毛蟲能存活的方案，必定也存在n-1隻毛毛蟲能存活的方案
設這n隻毛毛蟲總共排放了A克二氧化碳、最虛弱的毛毛蟲忍受度是B
那麼這個方案滿足B>=A/n
所以就拔走最肥、排放最多的毛毛蟲
由於這隻毛毛蟲的排放量ax>=A/n
可知此不等式左邊只會變大、右邊只會變小，一直到n=1都會成立

循著這個思路先將毛毛蟲按忍受度由小到大排序，按排放量建heap
二分答案並且檢驗
能放n隻毛毛蟲就return true，不行就從heap拔走最肥的蟲
由於「最低忍受是x、有n隻蟲的組合，是所有忍受>=x蟲子裡排放最少的n隻」
如此算法得解.....

.
.
.
.
[作法二]
這題還沒完
我們學術長的code長度和運行時間都是我的一半
我問了他用了甚麼神妙的做法可以那麼方便又快呢？
一問發現他的方法竟和我非常相似！

「照排放量由小到大、對忍受度建heap，掃過去箱子滿了就拔走虛弱的蟲，我也不會證明」

code相當短相當好懂
我腦筋一轉，只要把證明我的關鍵命題稍加修改：
「最低忍受是x的最佳組合，是所有忍受>=x蟲子裡排放最少的數隻」
如此一來就不需要二分答案O(nlgnlgn)，可以一次過去O(nlgn)解決了

[結論]
「當你手上有一把槌子的時候，所有的東西看上去都像釘子」
說明一個程序員每每學會新的技巧，很容易把遇到的不管甚麼問題都槌槌看能不能解決
有了這次經驗我會節制一點不要沉迷最小平均值環的漂亮方法O~O