a961. P3 叫我神偷 - 旦旦解題農場

內容

有個小偷，他誓言要偷爆整個孵蛋社區的所有住戶。

但身為一個有著雄心壯志的大盜，才不屑走回他偷過的房屋。

每一個住戶都有一個門牌號碼，房屋的排列方式是將門牌依照二元搜尋樹的規則所排列。

已知這個住戶左邊住的住戶編號必小於自己，右邊所有住戶的編號必大於自己。

現在給你他們建造的順序，也就是說，我們以二元搜尋樹的方式去建造所有住屋。

現在，請問你，這個胸懷大志的神偷大盜最多能偷幾間房屋 (他只能從根開始走)。

以及他要偷完最少幾個房屋才能偷到他的目標 (例如：若目標是根則答案是 $0$)。

輸入說明

第一行給兩個正整數 $T$、$Q$

代表有 $T$ 間房屋，共 $Q$ 筆詢問

第二行共有 $T$ 個正整數

代表房屋建造的順序

接下來有 $Q$ 行，每行一個正整數，表示要偷的目標

輸出說明

第一行輸出他能偷的最大間數

接下來 $Q$ 行

輸出他要偷完最少幾個房屋才能偷到他的目標

若這個目標不在這個社區中請輸出 $-1$

範例輸入

範例輸出

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <10M

提示：

對於前 $30\%$ 測資：$T\ ,\ Q \leq 100$，且偷的房屋必存在於社區中

對於 $100\%$ 測資：$T\ ,\ Q \leq 10^5$，且測資中所出現的所有數字皆為 $\in int$ 的正整數，門牌號碼保證不重複

標籤:

apcs 模擬 tree

出處:

[管理者：

frankie (34104)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」