LeetCode 1642. 可以到达的最远建筑（二分查找 / 优先队列贪心）

输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：
- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。

示例 2：
输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出：7

示例 3：
输入：heights = [14,3,19,3], bricks = 17, ladders = 0
输出：3
 
提示：
1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    	int l = 1, r = heights.size()-1, ans = 0, mid;
    	while(l <= r)
    	{
    		mid = l +((r-l)>>1);
    		if(canjump(heights, bricks, ladders, mid))
    		{	// 这些材料可以跳到 mid
    			ans = mid;
    			l = mid+1;
    		}
    		else
    			r = mid-1;
    	}
    	return ans;
    }
    bool canjump(vector<int>& heights, int bricks, int ladder, int dest)
    {
    	vector<int> g;
    	for(int i = 1; i <= dest; i++)
    		if(heights[i]-heights[i-1] > 0)
    		    g.push_back(heights[i]-heights[i-1]);
    	sort(g.begin(), g.end(), greater<int>());
        int i = 0;
    	for(; i < g.size(); i++)
    	{
    		if(ladder)
    			ladder--;//先用梯子，爬较高的
    		else if(bricks-g[i] >= 0)
    			bricks -= g[i];//再用砖块
            else if(bricks-g[i] < 0)
                break;//都没有了
    	}
    	return i == g.size();//可以完成任务
    }
};

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    	priority_queue<int,vector<int>,greater<int>> q;//小顶堆
    	int needbricks = 0;
    	for(int i = 1; i < heights.size(); i++) 
    	{
    		int h = heights[i]-heights[i-1];
    		if(h > 0)
    		{
    			q.push(h);
    			if(q.size() > ladders)
    			{
    				needbricks += q.top();
    				q.pop();
    			}
    			if(needbricks > bricks)
    				return i-1;
    		}
    	}
    	return heights.size()-1;
    }
};