✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线100+套真题改编解析，后续会持续更新的

春秋招合集 -> 互联网必备刷题宝典🔗

题目一：小兰的咖啡烘焙挑战

1️⃣：预处理数组的前后缀最小值，优化查询效率

2️⃣：考虑单机和双机两种策略，选择时间最短的方案

3️⃣：利用前后缀分解避免重复计算，实现O(n)时间复杂度

难度：中等

这道题目的核心在于理解两种烘焙策略的本质差异。通过前后缀预处理技巧，我们可以高效地为每台机器找到最优的搭配方案。关键是要认识到对于每个位置，我们需要在其前面和后面找到最小值，这正是前后缀处理的经典应用场景。

题目二：小兰的魔法花园

1️⃣：识别同余动态规划问题的特征，关注模数而非具体数值

2️⃣：使用记忆化搜索优化递归过程，避免重复计算

3️⃣：状态转移考虑移除和保留两种选择，选择代价最小的方案

难度：中等

这道题目结合了动态规划和数论知识，需要理解同余的性质。关键洞察是我们只需要关心余数而不是具体的数值，这大大减少了状态空间。通过记忆化搜索，我们可以有效地处理所有可能的选择组合，找到最优解。

01. 小兰的咖啡烘焙挑战

问题描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例输入

3
2 5 9
4 3 6

3
2 5 7
2 8 6

样例输出

3

4

数据范围

题解

这道题的核心思想是考虑两种策略：单机烘焙和双机并行烘焙。

对于双机并行的情况，我们需要选择一台机器烘焙 咖啡豆，另一台机器烘焙 咖啡豆。关键是要让 尽可能小。

解决方案是使用前后缀预处理：

1. 预处理 数组的前缀最小值和后缀最小值
2. 对于每个位置 ，如果选择第 台机器烘焙 咖啡豆，那么可以选择的 咖啡豆机器是前面或后面的最小值
3. 同时考虑单机烘焙的情况，即

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

# 读取输入数据
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

# 计算后缀最小值数组
suf = [0] * (n + 1)
suf[n] = float('inf')
for i in range(n - 1, -1, -1):
    suf[i] = min(suf[i + 1], y[i])

# 初始化答案和前缀最小值
ans = min(x[i] + y[i] for i in range(n))  # 单机情况
pre = float('inf')

# 遍历每个位置，计算双机并行的最优解
for i in range(n):
    # 当前机器烘焙a，其他机器烘焙b的最小时间
    cur = max(x[i], min(pre, suf[i + 1]))
    ans = min(ans, cur)
    pre = min(pre, y[i])

print(ans)

• Cpp

#include 
#include 
#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 读取两个数组
    vector x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> y[i];
    
    // 预处理后缀最小值
    vector suf(n + 1);
    suf[n] = 1e9;
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = min(suf[i + 1], y[i]);
    }
    
    // 计算答案
    int ans = 1e9, pre = 1e9;
    
    for (int i = 0; i < n; i++) {
        // 单机烘焙
        ans = min(ans, x[i] + y[i]);
        // 双机并行
        ans = min(ans, max(x[i], min(pre, suf[i + 1])));
        pre = min(pre, y[i]);
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取数据
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            y[i] = sc.nextInt();
        }