华为OD机试 - 导师请吃火锅 - 逻辑分析（Java 2023 B卷 200分）

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

入职后，导师会请你吃饭，你选择了火锅。火锅里会在不同时间下很多菜. 不同食材要煮不同的时间，才能变得刚好合适。你希望吃到最多的刚好合适的菜，但你的手速不够快，用 m 代表手速，每次下手捞菜后至少要过 m 秒才能再捞(每次只能捞一个)。那么用最合理的策略，最多能吃到多少刚好合适的菜?

二、输入描述

第一行两个整数 n，m，其中 n 代表往锅里下的菜的个数，m 代表手速。 (1<n，m< 1000)

接下来有 n 行，每行有两个数 x，y 代表第 x 秒下的菜过 y 秒才能变得刚好合适。

(1<x,y< 1000)

三、输出描述

输出一个整数代表用最合理的策略，最多能吃到刚好合适的菜的数量。

1、输入

3 2
1 2
2 1
3 2

2、输出

3、说明

往锅里下的菜的个数3，手速2；
第1秒的时候下入菜品1，2秒后熟了；
第2秒的时候下入菜品2，1秒后熟了；
第3秒的时候下入菜品3，2秒后熟了；
第一种菜品和第二种菜品只能吃到一种，第三种菜品可以吃到；
输出2。

四、解题思路

通过java8 Stream表达式（简洁/方便/上档次）快速拆解输入行；

五、Java算法源码

public class OdTest03 {

    /**
     * 第一行两个整数 n，m，其中 n 代表往锅里下的菜的个数，m 代表手速。
     * 接下来有 n 行，每行有两个数 x，y 代表第 x 秒下的菜过 y 秒才能变得刚好合适。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int n = Integer.valueOf(input[0]);
        int m = Integer.valueOf(input[1]);

        int[] suit = new int[n];
        for (int i = 0; i < n; i++) {
            suit[i] = sc.nextInt() + sc.nextInt();
        }

        System.out.println(getResult(n, m, suit));
    }

    public static int getResult(int n, int m, int[] suit) {
        Arrays.sort(suit);
        // 第1个合适的菜必吃
        int count = 1;
        int pre = 0;
        for (int i = 1; i < suit.length; i++) {
            if (suit[i] >= suit[pre] + m) {
                // 如果想要捞本次合适的菜，则必须要与上次捞菜的时间差大于等于m，注意这里是suit[pre] + m ，而不是suit[i-1] + m
                count++;
                // 如果本次捞了菜，则更新缓存本次捞菜的时间点
                pre = i;
            }
        }
        return count;
    }
}