[HackerRank]服務車道(Service Lane)

題目描述

卡爾文正在101號高速公路上開著他最愛的車子。他注意到他愛車的引擎檢查燈亮了,他想要儘快去處理它,以免發生危險。幸運的是,有條服務車道就在高速公路旁邊,與高速公路平行。服務車道的長度為N單位,其中每個段落的寬度都不一樣。

卡爾文從任意進出某一段的服務車道。我們把服務車道的段落用索引i來表示,從服務車道出去的段落用j表示,i大於等於0,j大於等於i。卡爾文在通過索引i到j(包含i和j)的服務車道段落,並不會在中途轉換車道。

卡爾文有三種車子,重型機車、汽車和卡車,它們的寬度分別是1、2和3,並直接用寬度來表示這三種車。

使用長度為N的width陣列,width[k]表示服務車道在第k段的寬度。卡爾文在服務車道行駛的時候不會超過1000個段落,包含進入和出去的段落。

若width[k]=1,只有重型機車可以通過第k段。
若width[k]=2,重型機車和汽車可以通過第k段。
若width[k]=3,卡爾文所有的車子都可以通過第k段。

給定卡爾文的車子進入和出去服務車道的索引值,輸出最大可以通過這段服務車道車子種類。

原題網址

https://www.hackerrank.com/challenges/service-lane

輸入格式

第一行包含兩個整數,N和T。N為高速公路的長度,同時也是服務車道的長度,範圍在2到100000之間(包含2和100)。T為測試資料的數量,範圍在1到1000之間(包含1和1000)。第二行輸出N個整數,表示width陣列,每個陣列的元素值的範圍在1到3之間(包含1和3)。

再來的T行,每行包含兩個整數,i和j。i是卡爾文的車子進入服務車道的段落索引值,j是從服務車道出來的段落索引值。i大於等於0,小於N;j大於等於i,小於N。

輸出格式

對每個測試資料進行計算,分別輸出其最大能通過服務車道的車子種類。

範例輸入

8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7

範例輸出

1
2
3
2
1

額外解釋

以下是高速公路和服務車道的示意圖:

(0, 3):最窄的段落是在索引2的位置,寬度只有1,所以只有重型機車可以通過。
(4, 6):最窄的段落是在索引5的位置,寬度只有2,所以最大只能讓汽車通過。
(6, 7):這段寬度都是3,所以所有車子都可以通過。
(3, 5):最窄的段落是在索引3和索引5的位置,寬度只有2,所以最大只能讓汽車通過。
(0, 7):最窄的段落是在索引2的位置,寬度只有1,所以只有重型機車可以通過。

解題概念

這題敘述很難理解,其實只要在width陣列的索引i到索引j元素中,找出最小值即可。可以使用線性搜尋的方式,逐一找出最小值。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章