連結：TOJ374 飢餓的Sana
題目：
一排食物陳列在前，每個食物各有一個飽食度一次需抓取一個區段的食物來吃，區段大小可以是1
整個區段的飽食度即為裏頭每個食物的飽食度總和
現在請你找出第K大(非嚴格)的飽食度為多少
做法：
昨天寫了spoj一題，利用TwoPointer找出不超過某數的最大區間連續和而這題要找的是第K大連續和，而且值都是正數，所以同樣地可以利用這個方法
在O(N)的複雜度算出有幾個區段>某數，也就是找出某數是第幾大的飽食度
那我們只要對這個某數二分搜，逐步縮小範圍，直到某數恰好是第K大為止
再重新算一下不超過某數的最大區間連續和，就是答案了
程式碼中greater_函數回傳某數是否不比第K大還要大(名次>K)
code:
沒有留言:
張貼留言