題目描述
卡爾文正在101號高速公路上開著他最愛的車子。他注意到他愛車的引擎檢查燈亮了,他想要儘快去處理它,以免發生危險。幸運的是,有條服務車道就在高速公路旁邊,與高速公路平行。服務車道的長度為N單位,其中每個段落的寬度都不一樣。
卡爾文從任意進出某一段的服務車道。我們把服務車道的段落用索引i來表示,從服務車道出去的段落用j表示,i大於等於0,j大於等於i。卡爾文在通過索引i到j(包含i和j)的服務車道段落,並不會在中途轉換車道。
卡爾文有三種車子,重型機車、汽車和卡車,它們的寬度分別是1、2和3,並直接用寬度來表示這三種車。
使用長度為N的width陣列,width[k]表示服務車道在第k段的寬度。卡爾文在服務車道行駛的時候不會超過1000個段落,包含進入和出去的段落。
若width[k]=2,重型機車和汽車可以通過第k段。
若width[k]=3,卡爾文所有的車子都可以通過第k段。
給定卡爾文的車子進入和出去服務車道的索引值,輸出最大可以通過這段服務車道車子種類。
原題網址
輸入格式
第一行包含兩個整數,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。
輸出格式
對每個測試資料進行計算,分別輸出其最大能通過服務車道的車子種類。
範例輸入
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7
範例輸出
2
3
2
1
額外解釋
以下是高速公路和服務車道的示意圖:
|高速公路|服務車道| -> 寬度 0: | |--| 2 1: | |---| 3 2: | |-| 1 3: | |--| 2 4: | |---| 3 5: | |--| 2 6: | |---| 3 7: | |---| 3
(0, 3):最窄的段落是在索引2的位置,寬度只有1,所以只有重型機車可以通過。
(4, 6):最窄的段落是在索引5的位置,寬度只有2,所以最大只能讓汽車通過。
(6, 7):這段寬度都是3,所以所有車子都可以通過。
(3, 5):最窄的段落是在索引3和索引5的位置,寬度只有2,所以最大只能讓汽車通過。
(0, 7):最窄的段落是在索引2的位置,寬度只有1,所以只有重型機車可以通過。
解題概念
這題敘述很難理解,其實只要在width陣列的索引i到索引j元素中,找出最小值即可。可以使用線性搜尋的方式,逐一找出最小值。
參考答案
import java.util.Scanner;
public class Solution {
public static void main(final String[] args) throws Exception {
final Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
int testCase = sc.nextInt();
final int width[] = new int[n];
for (int i = 0; i < n; ++i) {
width[i] = sc.nextInt();
}
while (testCase-- > 0) {
final int i = sc.nextInt();
final int j = sc.nextInt();
int min = Integer.MAX_VALUE;
for(int k = i; k <= j; ++k){
final int w =width[k];
if(w < min){
min = w;
}
}
System.out.println(min);
}
}
}