💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍠 小米秋招第一场笔试，来啦！！！

🍥 本次小米有两套卷，算法和其他岗位是不同的卷子，本套给大家带来小米 研发岗 的卷

1️⃣ 典中典之前后缀最小值，当然也可以用带log的写法方便点

2️⃣ 同余类型的动态规划，第一次接触的小伙伴可能就蒙圈了，实际上不难

☕️ 01.K小姐的咖啡烘焙挑战

问题描述

K小姐是一位咖啡爱好者，她每天都要品尝两种不同的咖啡豆： 和 。她拥有 台不同的咖啡烘焙机，每台机器烘焙不同咖啡豆的时间各不相同。第 台烘焙机烘焙 咖啡豆需要 分钟，烘焙 咖啡豆需要 分钟。

为了尽快品尝到这两种咖啡，K小姐可以选择两种方案：

1. 选择两台不同的烘焙机 和 同时工作，分别烘焙 和 咖啡豆，此时总耗时为 。
2. 选择一台烘焙机 依次烘焙 和 咖啡豆，此时总耗时为 。

请帮助K小姐计算出最短的烘焙时间，使她能尽快品尝到这两种咖啡。

输入格式

第一行一个正整数 ，表示咖啡烘焙机的数量。

第二行 个正整数 ，表示每台烘焙机烘焙 咖啡豆的时间。

第三行 个正整数 ，表示每台烘焙机烘焙 咖啡豆的时间。

输出格式

输出一行一个正整数，表示最短的烘焙时间。

样例输入

3
2 5 9
4 3 6

样例输出

3

样例输入

3
2 5 7
2 8 6

样例输出

4

数据范围

题解

前后缀预处理

解题思路如下：

1. 计算 数组的后缀最小值数组 ，其中 表示从第 个元素到最后的最小值。
2. 计算 数组的前缀最小值数组 ，其中 表示从第一个元素到第 个元素的最小值。
3. 遍历 数组，对于每个 ，我们需要在 数组中找一个不同下标的最小值。这个最小值可能是 （ 后面的最小值）或 （ 前面的最小值）。
4. 同时，还需要考虑使用单个烘焙机烘焙两种咖啡豆的情况，即 。
5. 最后的结果是上述所有情况的最小值。

这种方法的时间复杂度是 ，

当然也有带 简单点的写法

参考代码

• 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]);