25届-9.05xiao米改编题(研法岗)
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 合集传送们 -> 🧷学长刷题笔记
🍒 本专栏已收集
140+套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞
🍠 小米秋招第一场笔试，来啦！！！
🍥 本次小米有两套卷，算法和其他岗位是不同的卷子，本套给大家带来小米
研发岗的卷1️⃣ 典中典之前后缀最小值，当然也可以用带log的写法方便点
2️⃣ 同余类型的动态规划，第一次接触的小伙伴可能就蒙圈了，实际上不难
☕️ 01.K小姐的咖啡烘焙挑战
问题描述
K小姐是一位咖啡爱好者，她每天都要品尝两种不同的咖啡豆： 和
。她拥有
台不同的咖啡烘焙机，每台机器烘焙不同咖啡豆的时间各不相同。第
台烘焙机烘焙
咖啡豆需要
分钟，烘焙
咖啡豆需要
分钟。
为了尽快品尝到这两种咖啡，K小姐可以选择两种方案：
- 选择两台不同的烘焙机
和
同时工作，分别烘焙
和
咖啡豆，此时总耗时为
。
- 选择一台烘焙机
。
请帮助K小姐计算出最短的烘焙时间，使她能尽快品尝到这两种咖啡。
输入格式
第一行一个正整数 ，表示咖啡烘焙机的数量。
第二行 个正整数
，表示每台烘焙机烘焙
咖啡豆的时间。
第三行 个正整数
，表示每台烘焙机烘焙
咖啡豆的时间。
输出格式
输出一行一个正整数，表示最短的烘焙时间。
样例输入
3
2 5 9
4 3 6
样例输出
3
样例输入
3
2 5 7
2 8 6
样例输出
4
数据范围
题解
前后缀预处理
解题思路如下：
- 计算
，其中
表示从第
个元素到最后的最小值。
- 计算
，其中
表示从第一个元素到第
- 遍历
，我们需要在
（
（
- 同时，还需要考虑使用单个烘焙机烘焙两种咖啡豆的情况，即
。
- 最后的结果是上述所有情况的最小值。
这种方法的时间复杂度是 ，
当然也有带 简单点的写法
参考代码
- Python
def min_roasting_time():
# 读取输入
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 计算b的后缀最小值
suf_b = [0] * (n + 1)
suf_b[n] = float('inf')
for i in range(n - 1, -1, -1):
suf_b[i] = min(suf_b[i + 1], b[i])
# 计算b的前缀最小值
pre_b = float('inf')
# 计算最小烘焙时间
min_time = min(a[i] + b[i] for i in range(n)) # 单机烘焙两种咖啡豆
# 遍历所有可能的组合
for i in range(n):
# 选择a[i]，然后在b中选择不同下标的最小值
min_time = min(min_time, max(a[i], min(pre_b, suf_b[i + 1])))
pre_b = min(pre_b, b[i])
return min_time
# 输出结果
print(min_roasting_time())
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入
int n = scanner.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
b[i] = scanner.nextInt();
}
// 计算并输出结果
System.out.println(minRoastingTime(n, a, b));
scanner.close();
}
public static int minRoastingTime(int n, int[] a, int[] b) {
// 计算b的后缀最小值
int[] sufB = new int[n + 1];
sufB[n] = Integer.MAX_VALUE;
for (int i = n - 1; i >= 0; i--) {
sufB[i] = Math.min(sufB[i + 1], b[i]);
}
// 计算最小烘焙时间
int minTime = Integer.MAX_VALUE;
int preB = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// 单机烘焙两种咖啡豆
minTime = Math.min(minTime, a[i] + b[i]);
// 选择a[i]，然后在b中选择不同下标的最小值
minTime = Math.min(minTime, Math.max(a[i], Math.min(preB, sufB[i + 1])));
preB = Math.min(preB, b[i]);
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
利益相关，专栏短期内将不再更新 文章被收录于专栏
本专栏短期内不再更新，请勿继续订阅
。
除非自己有特别明确的职业发展技术规划，否则两年硕士就和国内本科plus版的感觉一样，这个项目做一下，那个项目做一下，每个技术只是“用过”，谈不上熟练使用。 相比之下感觉国内硕士首先时间长一点，其次一般实验室导师总有研究方向，所以技术方面就会“专精”一点，哪怕自己摆烂被导师推着也多少能学点。
不过我觉得海硕的优势就是自由度高，想科研自己找教授，想实习自己找，甚至很多学制也比较灵活，读个两三年都行，不存在找到实习导师不放的情况，属于是上限高下限低了
投递谷歌等公司10个岗位 >
查看3道真题和解析