回分類題庫
h193: D.分裂吧,樹堆
關鍵字: NPSC 2018 高中組初賽

測資點 : 6 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 6 Times / 6 Users | Submit : 60 Times / 10 Users | Accepted rate : 60%
題目加入時間 : 2020-05-06 13:12

Content: 简体中文

「分裂吧,樹堆」是一部在 NPSC 國很賣座的電影。電影大致的內容是:主角,NPSC 國的程式競賽選手們,在使用「分裂∕合併式樹堆」(merge-split treap)寫題目時,寫出 bug,發現 bug,de 出 bug 的勵志過程。

NPSC 國的程式競賽選手們使用「分裂∕合併式樹堆」寫題目的狂熱程度已經無法使用文字來形容,例如最簡單的 RMQ 問題(Range Minimum/Maximum Query,區間最大/最小值問題),他們會直接熟練的把樹堆模板打上去,把要維護的數值好好維護一下後,就上傳了。

有一天,主角們在著名的 NOJ(NPSC Online Judge)上面看到一道難題,看完題目之後,他們一如往常,直接把樹堆模板打上去。在對自己的程式碼自信滿滿,不測試範例測試資料的情況下,直接上傳程式碼。

結果得到 No - Wrong Answer 。

你,對於看到主角們使用樹堆上傳得到 Wrong Answer 的結果並不感到太意外,但是,你還是對主角們正在寫的難題感到興趣,題目如下:

現在 NOJ 的創辦者小 T 有 N 個樹堆,樹堆以 1 到 N 編號,第 i 個樹堆的大小為 si,第 i 個樹堆裡面的數字全部都是 i 。 

小 T 擁有的操作如下:

現在,小 T 想要藉由上述的兩個操作,產生出一個大小恰好為 K 的樹堆,並且這個樹堆的數字至多出現兩種不同的數字。如果小 T 需要使用操作的話,分裂操作一定要在合併操作之前使用完畢。當然,如果有很多種方法可以達成的話,小 T 會希望花費的代價越少越好。

主角們對於上面的樹堆問題感到頭痛。而你認為你一定可以解出這道問題的。於是,勇敢的你,開始寫了這題,也即將掉入寫出 bug,發現 bug,de 出 bug 的有限輪迴之中。 

Input:

輸入的第一行包含兩個正整數 N, K,代表電影的題目中,樹堆的數量,以及小 T 希望產生出來的樹堆大小。

接下來的一行,有 N 個整數,第 i 個整數為 si,代表第 i 個樹堆的大小。

接下來的一行,有 N 個整數,第 i 個整數為 pi,代表分裂第 i 個樹堆所需要的代價。 

Output:

針對每組測試資料請輸出一行結果,如果無法達成電影的題目中小 T 的心願(產生出一個大小恰好為 K 的樹堆),請輸出 −1 ,否則請輸出一個整數,代表產生出大小恰好為 K 的樹堆的最小代價。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 7
1 2 3
4 5 6
3 7
4 5 6
1 2 3

Sample Output :

-1
1

Hint :

Author :

NPSC 2018 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum