尚未解答計算數學 Problem Solving- 紅白彩帶 (APCS201902)
計算數學 Problem Solving- 紅白彩帶 (APCS201902)
給定彩帶的長度 N 和每一格的顏色(0=白，1=紅)，K次的著色(保證會在白色格子塗紅)，
輸出的兩個數字分別為每次著色後最長和最短的紅色區間長度總和。
這題會用到 DSU 連通的概念，維護每次著色後最長的紅色區間長度問題不大。
但問題點在於維護最短區間長度。
因為著色的關係，導致最多2個區間合併，代表 RootID 的長度會被改變。
又因為格子個數最多會有 1e5 個，暴力法理論上應該不可行。
我只想到 Mapping HEAP 這個資料結構(不確定有沒有這種東西...)。
基礎的 HEAP 資料結構加上一個映射陣列( mapp[RootID]=這個 RootID在HEAP的位置 )
這個 HEAP 只維護 每個 Group 的代表ID 並且依照長度維護(越小越上層)。
保證某個 RootID 長度被改變時是 ㏒N (HeapDown)，
或是因為區間合併導致需要刪除某個存在 HEAP 內的 RootID 時是 ㏒N (HeapUp+Down)。
不過考慮到這題屬 APCS，應該存在某種合理的資料結構應付上述需求?
至少不是要當場寫這種 Mapping HEAP吧...
最後附上程式碼：https://www.codepile.net/pile/NG2lD4rl
0個答案
計算數學 Problem Solving- 紅白彩帶 (APCS201902)
