🎯 前言

🏆 《华为机试真题》专栏含2023年牛客网面经、华为面经试题、华为OD机试真题最新试题。

🏆 华为机试有三道题，第一道和第二道属于简单题，分值为100分，第三道为困难题，分值为200分，总分400分，150分钟考试时间。

🏆 如果您在准备华为的面试，期间有想了解的可以私信我，我会尽可能帮您解答，也可以给您一些建议！

🎯 题目描述

入职后，导师会请你吃饭，你选择了火锅，火锅里会在不同时间下很多菜。

不同食材要煮不同的时间，才能变得刚好合适。你希望吃到最多的刚好合适的菜，但你的手速不够快，用m代表手速，每次下手捞菜后至少要过m庙才能在捞（每次只能捞一个）。

那么用最合理的策略，最多能吃到多少刚好合适的菜？

输入描述：
第一行两个整数n，m，其中n代表往锅里下的菜的个数，m代表手速。
接下来有n行，每行有两个数x，y代表第x秒下的菜过y秒才能变得刚好合适。
（1 < n, m < 1000）
（1 < x, y < 1000）

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

🎯 解题思路

这道题可以采用贪心算法的思想：优先选择用时短而又未烧焦的菜品，这样可以最大限度地增加吃下的数量。

具体操作如下：

对每个菜品按煮的时间从小到大排序；
开始吃菜：每当你要夹菜时，先找到煮好的、用时最短的菜夹起来吃掉，如果当前没有符合条件的菜，等待一段时间后再试；
继续等待、夹菜，直至所有菜品都被你夹完或已经烧焦。

📝下面是一个例子输入及输出：
输入：

输出：

这组输入中有5个菜品，你的手速为5，下菜和煮菜的时间分别在每一行中输入。按照上述代码的实现，算法会先按照下菜的时间排序，然后夹取用时最短的菜，直到所有菜品都被夹完或已经烧焦。在这个例子中，你可以吃掉的最多菜品数量为4，分别是第一个、第二个、第三个和第五个菜品。第四个菜品需要等待太久导致烧焦了，所以不能被计入菜品数量。

📙 Python实现代码

m, n = map(int, input().split())# 定义一个列表存储每个菜品的信息（下菜品的时间和煮好的时间）
dishes = []
for i in range(m):
# 注意这里要map转换成int类型
dishes.append(list(map(int, input().split())))# 对菜品按照下菜品的时间从小到大排序
dishes.sort(key=lambda x:x[0])# 定义一个变量记录吃掉多少道菜
count = 0
# 定义一个变量存储当前时间
cur_time = 0
# 开始吃菜
for dish in dishes:
if cur_time + n <= dish[1]:
# 如果当前时间加上吃菜的时间小于等于煮好的时间，说明这个菜未烧焦，夹起来吃掉
cur_time += n
count += 1
elif dish[1] > cur_time:
# 否则，等待直到这道菜煮好后再吃掉它，更新当前时间
wait_time = dish[1] - cur_time
cur_time = dish[1]
cur_time += n
count += 1# 输出吃掉的菜品数量
print(count)

📗 Java实现代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] dishes = new int[m][2];for (int i = 0; i < m; i++) {dishes[i][0] = sc.nextInt();dishes[i][1] = sc.nextInt();}Arrays.sort(dishes, (a, b) - > a[0] - b[0]);int count = 0, cur_time = 0;for (int i = 0; i < m; i++) {if (cur_time + n <= dishes[i][1]) {cur_time += n;count++;} else if (dishes[i][1] > cur_time) {int wait_time = dishes[i][1] - cur_time;cur_time = dishes[i][1];cur_time += n;count++;}}System.out.println(count);}
}

📘 C语言实现：

#
include# includeint cmp(const void * a,const void * b) {int * pa = (int * ) a;int * pb = (int * ) b;return pa[0] - pb[0];
}int main() {int m, n;scanf("%d%d", & m, & n);int * * dishes = (int * * ) malloc(m * sizeof(int * ));for (int i = 0; i < m; i++) {dishes[i] = (int * ) malloc(2 * sizeof(int));scanf("%d%d", & dishes[i][0], & dishes[i][1]);}qsort(dishes, m, sizeof(int * ), cmp);int count = 0, cur_time = 0;for (int i = 0; i < m; i++) {if (cur_time + n <= dishes[i][1]) {cur_time += n;count++;} else if (dishes[i][1] > cur_time) {int wait_time = dishes[i][1] - cur_time;cur_time = dishes[i][1];cur_time += n;count++;}}printf("%d\n", count);for (int i = 0; i < m; i++) {free(dishes[i]);}free(dishes);return 0;
}