→ medama: 大師 02/20 23:38
推 ILoveErr: 大師 02/20 23:39
※ 編輯: DJYOSHITAKA (114.137.252.52 臺灣), 02/20/2024 23:39:29
→ JIWP: 大師 02/20 23:45
推 JerryChungYC: 大師 02/20 23:57
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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.252.52 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708443520.A.88A.html