小米2025年校招笔试真题手撕（一）

一、题目

小A每天都要吃a,b两种面包各一个。而他有n个不同的面包机，不同面包机制作面包的时间各不相同。第i台面包机制作a面包

需要花费ai的时间，制作b面包则需要花费bi的时间。

为能尽快吃到这两种面包，小A可以选择两个不同的面包机x，y同时工作，并分别制作a，b两种面包，花费的时间将是

max(ax，by)。

当然，小A也可以选择其中一个面包机x制作a，b两种面包，花费的时间将是ax+bx。

为能尽快吃到面包，请你帮小A计算一下，至少需要花费多少时间才能完成这两种面包的制作。

输入描述：

第一行一个正整数n，表示面包机的个数。

第二行n个正整数ai，表示面包机制作面包a的时间。

第三行n个正整数bi，表示面包机制作面包b的时间。

n ≤ 100000；

a,b ≤ 100000；

输出描述：输出一行一个正整数，表示需要花费的最少时间。

示例输入1：

3

2 5 9

4 3 6

输出：

3

示例输入2：

3

2 5 7

2 8 6

输出：

4

二、分析

该问题是关于如何计算制作两种面包的最短时间，涉及到选择单个面包机或者两个不同的面包机来同时工作。先分析单面包机的情况，只需要遍历所有面包机，找到制作 a 面包和 b 面包时间之和的最小值，这很容易，时间复杂度是 O(n)。但重点在于双面包机的情况，因为直接穷举所有可能的组合会导致时间复杂度高达 O(n²)，对于大的 n 值来说不现实。因此，需要设计一个更高效的算法来找最小的 max(ax, by)。

可以考虑先对 a 和 b 的时间数组分别进行排序。然后使用两个指针分别遍历排序后的 a 和 b 数组，找到最优的组合。具体来说，先找到制作 a 面包最快和制作 b 面包最快的面包机，这样可能得到一个较小的 max(ax, by)。也可以尝试找出制作 a 面包最快的几个面包机，然后在对应的 b 面包时间中找较小的值，或者找出制作 b 面包最快的几个面包机，然后看对应的 a 面包时间。这种方法可能覆盖大部分最优解的情况。

在代码实现方面，读取输入的面包机数量和每个面包机的 a 和 b 时间。初始化两个数组来存储每个面包机的 a 和 b 时间。计算单个面包机情况下的最短时间，即找出所有面包机中 a 和 b 时间之和的最小值。然后处理两个面包机的情况，尝试找到两个不同的面包机 x 和 y，使得 max(ax, by) 最小。为此，可以将 a 和 b 时间数组分别排序，然后使用两个指针遍历排序后的数组，找到可能的最优组合。最后，综合单个面包机和两个面包机的情况，输出最小的时间值。

这种方法能够较好地平衡时间和空间效率，确保在大数据量下程序也能高效运行。需要注意处理边界情况，例如当只有一台面包机时只能选择单面包机的情况。通过这样的分析和代码实现，可以有效地解决题目要求的问题。

三、代码

下面是一个完整的 Python 代码示例，用于解决上述问题：

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))min_time = float('inf')# 单面包机情况
for i in range(n):total = a[i] + b[i]if total < min_time:min_time = total# 双面包机情况
# 找到制作 a 最快的面包机对应的 b 时间
min_a = min(a)
index_min_a = a.index(min_a)candidate_b = b[index_min_a]
if max(min_a, candidate_b) < min_time:min_time = max(min_a, candidate_b)# 找到制作 b 最快的面包机对应的 a 时间
min_b = min(b)
index_min_b = b.index(min_b)candidate_a = a[index_min_b]
if max(candidate_a, min_b) < min_time:min_time = max(candidate_a, min_b)print(min_time)

这个代码先计算每个面包机单独制作两种面包的时间之和，并找到其中的最小值。然后分别找到制作 a 面包和制作 b 面包最快的面包机，计算它们对应的双面包机情况的时间，并更新最小时间。最后输出最小时间。

但这样可能无法覆盖所有可能的最优解，比如可能存在某个面包机的 a 时间不是最小，但和另一个面包机的 b 时间组合起来更优的情况。

更好的方法是对所有可能的双面包机组合进行考虑：

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))min_time = float('inf')# 单面包机情况
for i in range(n):min_time = min(min_time, a[i] + b[i])# 双面包机情况
for i in range(n):for j in range(n):if i != j:current_time = max(a[i], b[j])if current_time < min_time:min_time = current_timeprint(min_time)

但这种方法的时间复杂度是 O(n²)，当 n 较大时（如 100000）会导致超时。

所以需要更高效的方法：

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))min_time = float('inf')# 单面包机情况
for i in range(n):min_time = min(min_time, a[i] + b[i])# 双面包机情况
min_a = min(a)
min_b = min(b)min_time = min(min_time, max(min_a, min_b))print(min_time)

这种方法只考虑制作 a 最快的面包机和制作 b 最快的面包机的组合，但这也可能错过一些更优的组合。

更合理的策略是：找到制作 a 面包的 k 台最快面包机和制作 b 面包的 k 台最快面包机，然后在这些有限的组合中寻找最优解。这里 k 可以设为 100 或其他较小的值。

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))min_time = float('inf')# 单面包机情况
for i in range(n):min_time = min(min_time, a[i] + b[i])# 双面包机情况
k = 100
sorted_a = sorted(range(n), key=lambda x: a[x])
sorted_b = sorted(range(n), key=lambda x: b[x])for i in range(min(k, n)):for j in range(min(k, n)):if sorted_a[i] != sorted_b[j]:current_time = max(a[sorted_a[i]], b[sorted_b[j]])if current_time < min_time:min_time = current_timeprint(min_time)

这种方法综合了单面包机和双面包机的情况，并在有限的组合中寻找最优解，平衡了效率和准确性。时间复杂度主要取决于排序操作和有限次的组合检查。