回分類題庫
g056: E.看動畫
關鍵字: NPSC 2009 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 38 Times / 29 Users | Submit : 180 Times / 53 Users | Accepted rate : 55%
題目加入時間 : 2011-12-26 15:02

Content: 简体中文

小米很喜歡看動畫,他會把看過的動畫都存到硬碟裡,這樣以後才可以再翻出來複習。但是因為他實在是有太多動畫了,一顆硬碟擺不下,所以他買了很多顆硬碟來存。為了方便以後尋找,每一個硬碟都有一個編號,還有上面存了哪些動畫,動畫是以集為單位,一部動畫可能有很多集,但是一集一定會放在同一顆硬碟不會分在兩顆。

有一天,當他想要把OOXX重看一遍時,發現一個麻煩的問題,動畫當然就是要從第一集開始一集集依序看完,但是不同集的動畫不一定放在同一個硬碟裡,因此要看完一部動畫可能會用到很多顆硬碟。硬碟當然是要接上電腦才能用,但是電腦的USB接頭是有限的,因此可能沒有辦法一次把全部的硬碟接上去,所以當你看完一集時可能需要抽換硬碟才能看到下一集。當然如果現在連在電腦上的硬碟已經有你要看的那一集那就可以不用換。因為一直換硬碟實在是太麻煩了,會影響看動畫的心情。所以他把他想看的動畫存在哪一顆硬碟中依序跟你講,希望請你寫一個程式來決定怎麼抽換硬碟才能使抽換次數降到最低。

舉例來說,動畫可能依序放在5 4 3 2 1這五個硬碟中,電腦上有三個USB接頭,最少需要兩次抽換才能看完整部動畫。方法如下,首先先把5 4 3接上電腦,之後把5 4拔掉換成2 1,這樣就可以全部看完。

Input:

第一行有一個整數代表總共有幾筆測試資料。
每一筆測試資料有兩行。
第一行有 N, M 兩個整數,N 代表動畫總共有幾集,M 代表有幾個USB接頭。
第二行有 N 個整數 A1 到 AN,代表依序要使用的硬碟編號。
N<1000000,M<100,0<= Ai <=10000

Output:

每一筆測試資料輸出一個整數,代表最少要抽換多少次硬碟。

Sample Input:help

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

Sample Output :

0
2

Hint :

Author :

NPSC 2009 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum