NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2018高中組初賽
 D.分裂吧,樹堆

作者 主題: D.分裂吧,樹堆  (閱讀 77 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 238
    • 檢視個人資料
D.分裂吧,樹堆
« 於: 五月 14, 2020, 09:15:23 am »

先處理特殊情況 N=1:
S0<K 輸出-1
S0=K 輸出0
S0>K 輸出P0

N>=2的情況:
先依照 S 值由大排到小,S 值相同的則依照 P 值由大排到小
如果前兩個的 S 相加之後小於 K,則輸出 -1,
接下來把這些數字切成兩段,
前面的是 Si > K,後面的則是 Si < K,
如果有找到 Si = K,則輸出 0。
前面 Si > K 的部分只要把該樹堆分裂即可,
因此找 Pi 最小的一個為 P1,
前面 Si < K 的部分則是需要兩個樹堆合併,
S 值相加之後大於 K 時才會有解,將 P 值較小的樹堆分裂,
這邊的最小值為 P2,
而若有一組 S 值相加之後等於 K,則 P2=0,
最後輸出 P1、P2 中較小的那個即可。
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2018高中組初賽
 D.分裂吧,樹堆