我们会有一个大致的概念:就是遇到跨度大尽量用梯子,遇到跨度小的采用砖头更合算。
我们现在只考虑需要爬升的楼(下降的楼可以忽略)。如果需要爬升的楼的数目<=ladders,那么是一定是可以到达的。如果我们需要爬升ladders+1座楼的时候,其中必然会有一次需要用到砖头。那么我们是在爬哪一幢楼的时候用砖头呢?显然,是跨度最小的那幢楼。并且一个很重要的结论是:无论未来会遇到什么样的楼(或高或低),这幢依靠砖头去爬的楼一定不会改变当初的决策。为什么呢?因为已经有ladders座楼的跨度比它大了,无论如何,这幢楼都不会有资格去使用梯子。
具体的算法是:我们逐个遍历楼层,将跨度依次放入一个优先队列中。如果队列的元素数目大于ladders,那么当前最小的元素必然需要用砖头来实现(隐含的意思就是其他元素可以用梯子来实现)。于是砖头的总数减去该跨度,并将该跨度从优先队列中弹出。前进的过程中不断重复这个过程,直至砖头不够用为止。