a068. E. 看動畫 加强版
標籤 :
通過比率 : 73人/120人 ( 61% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-03-08 22:48

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

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

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

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

 N ≤ 1000000, M ≤ 10000, 0 ≤ An ≤ 100000, 0 < T < 10

輸出說明
每一筆測試資料輸出一個整數,代表最少要抽換多少次硬碟。
範例輸入 #1
2
5 5
1 2 3 4 5
5 3
5 4 3 2 1
範例輸出 #1
0
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 30.0s , <50M
提示 :

NPSC d592: E. 看動畫 加强版

標籤:
出處:
NPSC 加强 [管理者: liouzhou_101 (王启圣) ]

本題狀況 本題討論 排行

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