🎯 前言

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

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

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

🎯 题目描述

某公司员工食堂以盒饭的方式供餐。
为将员工取餐排队时间降为0，食堂的供餐速度必须要足够快。
现在需要根据以往员工取餐的统计信息，计算出一个刚好能达到排队时间为0的最低供餐速度；
即，食堂在每个单位时间内必须至少做出多少份盒饭才能满足要求。

输入描述：
第一行为一个正整数N，表示食堂开餐时长；
第二行为一个正整数M，表示开餐前食堂已经准备好的盒饭数量；
第三行为N个正整数，用空格分割，依次表示开餐时间内按时间顺序每个单位时间进入食堂取餐的人数。

输出描述：
一个整数，能满足题目要求的最低供餐速度。(每个单位时间需要做出多少份盒饭)。

🎯 解题思路

题目要求根据员工取餐的统计信息计算能够达到排队时间为0的最低供餐速度，即食堂每个单位时间内最少要做出多少份盒饭。可以参考以下思路实现：

首先，输入食堂的开餐时长和开餐前准备好的盒饭数量。
然后，按照时间顺序输入每个单位时间内进入食堂取餐的人数。
我们可以使用二分查找来找到能够达到排队时间为0的最低供餐速度，即每个单位时间内最少要做出多少份盒饭。
对于每个可能的供餐速度，我们可以模拟食堂供餐的过程，计算出每个单位时间结束后排在队列中的员工数量。如果排在队列中的员工数量等于0，说明该供餐速度能够达到排队时间为0。
最后，根据比较结果调整二分查找的上界和下界，直到得到最低供餐速度。

输入：
3
14
10 4 5

输出：
3

📙 Python代码实现

# 模拟供餐的过程
def simulate(m, nums, speed):n = len(nums)m -= nums[0]for i in range(1, n):m += speedif m >= nums[i]:m -= nums[i]else:return Falsereturn True# 二分查找最低供餐速度
def binary_search(m, nums, left, right):while left < right:mid = (left + right) // 2if simulate(m, nums, mid):right = midelse:left = mid + 1return left# 输入开餐时长和开餐前准备好的盒饭数量
n = int(input())
m = int(input())# 输入每个单位时间内进入食堂取餐的人数
nums = list(map(int, input().split()))# 二分查找最低供餐速度
left, right = 1, max(nums)
speed = binary_search(m, nums, left, right)# 输出结果
print(speed)

📗 Java代码实现

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}// 二分查找最低供餐速度int left = 1, right = Arrays.stream(nums).max().getAsInt() + m;while (left < right) {int mid = (left + right) / 2;if (simulate(m, nums, mid)) {right = mid;} else {left = mid + 1;}}// 输出结果System.out.println(left);}// 模拟供餐的过程private static boolean simulate(int m, int[] nums, int speed) {int n = nums.length;m -= nums[0];for (int i = 0; i < n; i++) {m += speed;if (m >= nums[i]) {m -= nums[i];} else {return false;}}return true;}
}

📘 C语言代码实现

# include
# include# define MAXN 1000// 模拟供餐的过程
int simulate(int m, int nums[], int n, int speed) {int idx = 0;m -= nums[0]for (int i = 0; i < n; i++) {m += speed;if (m >= nums[i]) {m -= nums[i];} else {return 0;}}return 1;
}int main() {int n, m;scanf("%d%d", & n, & m);int nums[MAXN];for (int i = 0; i < n; i++) {scanf("%d", & nums[i]);}// 二分查找最低供餐速度int left = 1, right = nums[0] + m;while (left < right) {int mid = (left + right) / 2;if (simulate(m, nums, n, mid)) {right = mid;} else {left = mid + 1;}}// 输出结果printf("%d\n", left);return 0;
}