#45131: 可能比較不同的解法


harlivy_forever (噴火水雞肉飯)

學校 : 國立嘉義高級中學
編號 : 160563
來源 : [118.171.216.72]
最後登入時間 :
2025-01-15 00:33:51
c875. 107北二2.裝置藝術 -- 107北二區桃竹苗資訊學科能力複賽 | From: [118.171.215.98] | 發表日期 : 2025-01-11 15:13

因為只能拿罐子不能加罐子,所以只要一直從還沒找過的塔中找當前高度最低的塔,把它兩側塔的高度弄到符合條件,同時更新需要拿掉的罐子數,這樣當所有塔都被找過一遍時就結束了。

可能有更好的實作方法,但我自己是用 priority_queue 裝 { 塔的高度, 塔的編號 } 的 pair,排列方式是高度由低到高,編號則不用管。當每次更新一座塔的高度時 (即拿掉一些罐頭),把新的 pair 放進 priority_queue 裡。不過這麼一來, prioirty_queue 裡一定會有相同一座塔的資訊(也就是說會有多個編號相同的 pair ,因為在一座塔的高度被更新後,它原先的資料還在 priority_queue 裡面)為了避免重複檢查同一座塔,要紀錄已經找過的塔的編號,然後在每次取 priority_queue 的 top 時,如果是已經找過的塔就 continue ,不更新兩側塔的高度。

我不是很會解釋,不過簡單來說就是:

  1. 建 priority_queue,每次挑出當前高度最矮的塔來檢視
  2. 如果這個塔還沒找過,就把它兩側塔的高度弄到符合題目條件,同時更新答案。如果兩側塔高度有變,把新的兩側塔的資訊塞進 priority_queue
  3. 如果這個塔已經找過了,就不進行第二步
  4. 等到所有塔都被找過一遍後,跳出循環,輸出答案
 
ZeroJudge Forum