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;
}