切換
舊版
前往
大廳
主題

ZeroJudge - d314: 海星 解題心得

Not In My Back Yard | 2020-06-22 00:45:24 | 巴幣 2 | 人氣 141

題目連結:


題目大意:
輸入有多列,每列會先給定一字串,代表一條指令。如果該指令是「END」,則代表測資結束;如果是「GIVE」,接著會給定一整數 X ,代表 Fuko 會送出一個滿意度 X 的海星;如果是「FIND」,則會給定一正整數 K ,代表要尋找先前送出的海星裡滿意度第 K 高的海星其滿意度。

對於每個「FIND」指令,輸出第 K 高的海星之滿意度。



範例輸入:
GIVE 1
GIVE 3
GIVE 5
FIND 1
FIND 2
FIND 3
GIVE 2
GIVE 4
FIND 1
FIND 2
FIND 3
FIND 4
FIND 5
END


範例輸出:
5
3
1
5
4
3
2
1


解題思維:
可以看到我們需要一個可以即時存取任意指定位置又可以快速排序的作法。如昨天提及的 C++ vector 之 insert 函式搭配二分搜尋法(Binary Search)。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作