c218. kevin 愛旅行 - 高中生程式解題系統

內容

kevin 很喜歡旅行，而且喜歡用一個劇酷的方式旅行
這次他挑了一個由 n 個城市組成的國家，並將其編號為(1 ~ n)
而旅行社大方地表示 kevin 可以任意決定旅遊起點並給了他一個序列 A 來表示旅遊的順序
其中的 Ai (1 <= i <= n)代表著到了 i 城市後下個要到的城市
但卻被 kevin 大師一眼看出序列中一個嚴重的邊緣現象：

1.裡面沒有任何地方會到城市 1
2.經過城市 1 後的下一個城市還是城市 1 (即 A1 = 1)

再看到這種安排後，kevin 覺得太奇怪了，為了想要一窺城市 1 的神秘
他跟旅行社提出了兩個要求：
1.不管 kevin 從哪個城市出發都會到達城市 1
2.為了長期觀察城市 1 的邊緣指數，在離開城市 1 後的 k 天後他將要回到城市 1

看到 kevin 這樣毫無頭緒的的要求，要重新訂製一個序列需要太高成本
不過現在你可以每次透過修改序列中的一個數字當作一個操作
身為一個其實跟kevin沒甚麼關係的你
你能幫 kevin 算算需要多少操作才可以達到 kevin 的要求嗎？

輸入說明

第一行有兩個數字 n , k ( 0 < n , m <= 5 * 10 ^ 5 )
分別代表城市的數量和kevin的要求天數
第二行是序列 A
其中 Ai 為到 i 城市後下個會到的城市
保證 A1 = 1
Ai (2 <= i <= n) ，則 2 <= Ai <= n

輸出說明

輸出一個數字代表要達到kevin要求的最少操作

範例輸入 #1

範例輸入 1 ：
9 1
1 4 2 3 5 5 5 7 7


範例輸入 2 ：
11 4
1 3 4 10 4 4 6 11 11 2 3

範例輸出 #1

範例輸出 1 ：
2


範例輸出 2 ：
2

測資資訊：

記憶體限制： 256 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 , <1M
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (6%): 1.0s , <10M
公開測資點#15 (6%): 1.0s , <10M
公開測資點#16 (6%): 1.0s , <10M
公開測資點#17 (6%): 1.0s , <10M
公開測資點#18 (6%): 1.0s , <10M

提示：

範測 1 中

若把序列改為 1 1 2 3 1 5 5 7 7

則可以使得從任意位置出發皆可到達城市1

而從城市1出發後經過1天即可回到城市1

範測 2 中

若把序列改為 6 3 4 10 4 4 6 11 11 1 3

則可以使得從任意位置出發皆可到達城市1

而從城市1出發後經過4天即可回到城市1 (1 -> 6 -> 4 -> 10 -> 1)

標籤:

出處:

[管理者： boook (boook) ]

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