[Java] 蓝桥杯ADV-155 算法提高上帝造题五分钟

问题描述
第一分钟，上帝说：要有题。于是就有了L，Y，M，C
第二分钟，LYC说：要有向量。于是就有了长度为n写满随机整数的向量
第三分钟，YUHCH说：要有查询。于是就有了Q个查询，查询向量的一段区间内元素的最小值
第四分钟，MZC说：要有限。于是就有了数据范围
第五分钟，CS说：要有做题的。说完众神一哄而散，留你来收拾此题
输入格式
第一行两个正整数n和Q，表示向量长度和查询个数
接下来一行n个整数，依次对应向量中元素：a[0]，a[1]，…，a[n-1]
接下来Q行，每行两个正整数lo，hi，表示查询区间[lo, hi]中的最小值，即min(a[lo],a[lo+1],…,a[hi])。
输出格式
共Q行，依次对应每个查询的结果，即向量在对应查询区间中的最小值。
样例输入
7 4
1 -1 -4 8 1 2 -7
0 0
1 3
4 5
0 6
样例输出
1
-4
1
-7
样例说明
第一个查询[0,0]表示求min{a[0]}=min{1}=1
第二个查询[1,3]表示求min{a[1],a[2],a[3]}=min{-1,-4,8}=-4
第三个查询[4,5]表示求min{a[4],a[5]}=min{1,2}=1
第四个查询[0,6]表示查询整个向量，求min{a[0..6]}=min{1,-1,-4,8,1,2,-7}=-7
数据规模和约定
1<=n<=1984，1<=Q<=1988，向量中随机整数的绝对值不超过1,000

Java

package adv155; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] query = new int[n]; int q = in.nextInt(); for (int i = 0; i < n; i++) { query[i] = in.nextInt(); } for (int i = 0; i < q; i++) { System.out.println(partMin(query, in.nextInt(), in.nextInt())); } in.close(); } public static int partMin(int[] query, int start, int end) { int min = query[start]; for(int i = start; i <= end; i++) { if (query[i] < min) { min = query[i]; } } return min; } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package adv155;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] query = new int[n];
        int q = in.nextInt();
        for (int i = 0; i < n; i++) {
            query[i] = in.nextInt();
        }

        for (int i = 0; i < q; i++) {
            System.out.println(partMin(query, in.nextInt(), in.nextInt()));
        }
        in.close();
    }

    public static int partMin(int[] query, int start, int end) {
        int min = query[start];
        for(int i = start; i <= end; i++) {
            if (query[i] < min) {
                min = query[i];
            }
        }
        return min;
    }

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版