【leetcode】可以到达的最远建筑 （贪心）

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

示例 1：

输入：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 <= 10^5
1 <= heights[i] <= 10^6
0 <= bricks <= 10^9
0 <= ladders <= heights.length

链接：https://leetcode-cn.com/problems/furthest-building-you-can-reach

思路分析：

从低处到高处时，有两种选择：砖块和梯子。
假设当前为 i, diff = h[i+1]-h[i]. diff > 0 时，可以选择消耗diff个砖块和1个梯子。
我们很容易可以想到，梯子性价比最高的用法就是尽可能用在diff值大的地方。因此可以想到：
假设梯子数量为k，我们当前所处位置为 i , 我们需要在[1,i]中找前k大的diff. 这个可以用小项堆实现。每走一步，都要维护一个前k大的小项堆，并记录前k大的总和。
直接上代码吧。

//梯子无视diff，因此diff越大用梯子性价比越高
//最小堆记录[1,i]前k大，ptot记录前k大总和
//tot记录高度差总和
//取bricks >= tot-ptot的最右边界

#define ll long long
class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
		ll tot = 0, ptot = 0;
		int ans = 0;
        int n = heights.size();
		priority_queue<int,vector<int>,greater<int>> q;
		for(int i = 1;i < n;i++)
		{
			int diff = heights[i]-heights[i-1];
			if(diff > 0)
			{
				tot += diff;
				if(q.size() < ladders) q.push(diff), ptot+=diff;
				else
				{
					if(!q.empty() && diff > q.top())
					{
						ptot -= q.top();
						q.pop();
						q.push(diff);
						ptot+=diff;
					}
				}
			}
            if(bricks >= tot-ptot) ans = i;
		}
		return ans;
    }
};