1642. Furthest Building You Can Reach
前幾天的
一開始想都不想直接DFS 當然是TLE 浪費了幾分鐘
後來想想應該就greedy 一開始先全用brick
當brick不夠用的時候 回頭把用最多brick的那一階換成梯子
大概是這樣 不過出來速度幾乎墊底捏==
感覺跟大部分人的solution差不多才是
我也懶得檢查ㄌ 我好爛
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int idx;
priority_queue<int> diffs;
for(idx=1; idx<heights.size(); idx++)
{
if(heights[idx-1] >= heights[idx])
{
continue;
}
else
{
int diff = (heights[idx] - heights[idx-1]);
// using bricks first
bricks = bricks - diff;
diffs.push(diff);
// check if bricks ran out
if(bricks < 0)
{
// use one ladder
if(!diffs.empty() && ladders>0)
{
int max_diff_bricks = diffs.top();
bricks += max_diff_bricks;
ladders -= 1;
diffs.pop();
}
else
{
// can't reach
break;
}
}
}
}
return idx-1;
}