[HackerRank]服務車道(Service Lane)

題目描述

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

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

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

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

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

原題網址

輸入格式

第一行包含兩個整數，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。

輸出格式

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

範例輸入

範例輸出

額外解釋

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

   |高速公路|服務車道|    ->    寬度

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);
        }
    }
}