題目描述

卡爾文正在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段。

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

原題網址

輸入格式

第一行包含兩個整數,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: |        |--|              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);
        }
    }
}