c065: 寶藏獵人 $(Treasure)$
Tags :
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2021-06-07 23:52

Content

串串和電電兩人最近迷上了尋寶,於是他們打算到一座神廟去尋寶,終於到了最後一個房間......

電電:「神器就在裡面嗎?」

串串:「好像是如此...」

兩人望向眼前一道雄偉的大門,前面有一個戴物臺,上面放了一根很長的石棍。

串串檢視了一下這道大門,發現門上有很多方形的孔,在這些孔的正中間有一段很古老的文字,串串仔細的讀過了一遍。

串串:「看來我們需要把這個石棍切成K段,然後把他們一一放進門上的孔,這樣門就可以打開了。」

電電:「話說這根棍子上有好多數字,這是什麼意思?」

串串:「上面規定說每一個棍子必須滿足一個條件:棍子上每個數字與在他前面比他大的最小數字距離不超過某個數字。」

電電:「某個數字?」

串串:「上面的字跡似乎已經無法辨認了,不過他有提到這個數字就是最佳解。」

電電:「話說如果那個數字前面沒有任何數字比他大呢?」

串串:「那就是當作0。」

電電:「如果在他前面比他大的最小數字有很多個呢?」

串串:「那就算最前面的數字。」

電電:「話說要怎麼區分棍子的前面在哪邊?」

串串:「上面有寫,反正你照我給你的順序算就對了。」

電電:「算什麼?」

串串:「那個數字阿。難道要我用猜的嗎?」

 

Input

第一行有2個數字N,K,表示棍子上有多少個數字以及門上鑰匙孔的數量。

第二行有N個數字,表示由前到後棍子上的數字$v_i$,相鄰數字之間的距離是1。

$1 \leq K \leq N \leq 500000$

$-10^9 \leq v_i \leq 10^9$

Output

輸出「那個數字」。

Sample Input
9 4
4 1 2 5 0 9 12 8 9
Sample Output
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 2.0s , <1M
公開 測資點#3 (10%): 2.0s , <10M
公開 測資點#4 (10%): 2.0s , <10M
公開 測資點#5 (10%): 2.0s , <10M
公開 測資點#6 (10%): 3.0s , <1M
公開 測資點#7 (10%): 3.0s , <10M
公開 測資點#8 (10%): 3.0s , <10M
公開 測資點#9 (10%): 3.0s , <1M
Hint :

範例說明:切成[4] [1 2 5] [0 9 12] [8 9]

子題一(20%):$K = 1$

子題二(80%):無其他限制。

Tags:
出處:
[管理者:
810848 (路過)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」