✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

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

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

电信

题目一：图书馆课程安排优化

1️⃣：对课程按开始时间排序，预处理后缀最小值和前缀最小持续时间

2️⃣：利用二分查找快速定位合适的课程安排

3️⃣：分别考虑两种安排顺序，取最优结果

难度：中等

这道题目的核心是课程安排的优化问题，需要理解两种课程的时间约束和选择策略。通过巧妙的预处理和二分查找，我们可以将暴力 O(nm) 的复杂度优化到 O((n+m)log(n+m))，适合处理大规模数据。

题目二：智慧农场灌溉系统

1️⃣：将二维问题转化为一维列求和问题

2️⃣：使用动态规划记录状态：上一列是否安装设备，是否处于待定状态

3️⃣：通过状态转移计算最优收益方案

难度：中等

这道题目结合了网格优化和动态规划思想，关键在于理解"相邻影响"的机制。通过将二维问题降维，我们可以用线性 DP 在 O(n) 时间内求解，展现了问题抽象和状态设计的重要性。

题目三：城市快递配送路径

1️⃣：使用 Dijkstra 算法处理带约束的最短路径问题

2️⃣：状态设计包含坐标和无人机使用次数

3️⃣：通过预排序和动态激活优化跳跃目标的查找

难度：中等偏难

这道题目是经典最短路径问题的变种，引入了特殊的"跳跃"机制。通过状态扩展的 Dijkstra 算法和巧妙的预处理优化，我们实现了 O(mn log(mn)) 的高效解法，体现了图论算法在路径规划中的应用。

01. 图书馆课程安排优化

问题描述

小兰是一名勤奋的大学生，为了提升学术水平，她计划在图书馆参加两种类型的学习课程：专业课程学习和通识课程学习。学校规定每位学生必须从这两类课程中各选择恰好一门参加，具体的参加顺序可以自由安排。

专业课程有多个时段可供选择，其中 表示第 个专业课程时段的最早可开始时间， 表示该时段的学习时长。

通识课程也有多个时段可供选择，其中 表示第 个通识课程时段的最早可开始时间， 表示该时段的学习时长。

课程学习的具体规则如下：

1. 学生可以在课程时段的最早开始时间或之后的任意时间开始学习该时段的内容。

2. 若某个课程在时间 开始学习，那么它将在 + 该时段学习时长时结束。

3. 完成一个课程学习后，学生可以立即开始下一个课程学习（若下一个已到最早开始时间），也可等待下一个到最早开始时间后再开始学习。

请编写代码返回学生完成这两门课程学习的最早可能结束时间。

输入格式

第一行包含一个整数，表示专业课程的数量 。

第二行包含 个空格分隔的整数，表示 。

第三行包含 个空格分隔的整数，表示 。

第四行包含一个整数，表示通识课程的数量 。

第五行包含 个空格分隔的整数，表示 。

第六行包含 个空格分隔的整数，表示 。

输出格式

输出一个整数，表示学生完成这两门课程学习的最早可能结束时间。

样例输入

2
2 8
4 1
1
6
3

样例输出

9

数据范围

题解

这道题的关键是要理解我们需要在两种课程中各选一门，并且可以灵活安排顺序。

首先分析问题的本质：我们有 个专业课程和 个通识课程，需要各选一个，目标是最小化总的结束时间。

假设我们选择了专业课程 和通识课程 ，那么有两种安排顺序：

1. 先上专业课程，再上通识课程
2. 先上通识课程，再上专业课程

对于第一种情况，专业课程结束时间为 ，然后通识课程最早可以在 时间开始，总结束时间为 。

类似地，第二种情况的总结束时间为 。

但是，如果我们暴力枚举所有 种组合，时间复杂度会达到 ，当 都达到 时会超时。

关键观察是：对于固定的一种顺序（比如先专业后通识），给定专业课程结束时间 ，我们想要找到一个通识课程 ，使得 最小。

这个问题可以通过预处理来高效解决：

1. 将通识课程按照开始时间排序
2. 对于 的情况，我们需要 最小
3. 对于 的情况，我们需要 最小，即 最小

通过预处理后缀最小值和前缀最小持续时间，我们可以在 时间内回答每个查询。

总时间复杂度为 。

参考代码

• Python

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

def solve():
    n = int(input())
    prof_start = list(map(int, input().split()))
    prof_dur = list(map(int, input().split()))
    
    m = int(input())
    gen_start = list(map(int, input().split()))
    gen_dur = list(map(int, input().split()))
    
    # 构建课程信息
    prof = [(prof_start[i], prof_dur[i]) for i in range(n)]
    gen = [(gen_start[i], gen_dur[i]) for i in range(m)]
    
    # 对通识课程按开始时间排序
    gen.sort()
    
    # 预处理通识课程的后缀最小和前缀最小持续时间
    suf_min = [0] * m
    suf_min[m-1] = gen[m-1][0] + gen[m-1][1]
    for i in range(m-2, -1, -1):
        suf_min[i] = min(suf_min[i+1], gen[i][0] + gen[i][1])
    
    pre_dur = [0] * m
    pre_dur[0] = gen[0][1]
    for i in range(1, m):
        pre_dur[i] = min(pre_dur[i-1], gen[i][1])
    
    def query_min(t):
        # 二分查找第一个开始时间 >= t 的通识课程
        l, r = 0, m
        while l < r:
            mid = (l + r) // 2
            if gen[mid][0] >= t:
                r = mid
            else:
                l = mid + 1
        
        res = float('inf')
        if l < m:  # 存在开始时间 >= t 的课程
            res = min(res, suf_min[l])
        if l > 0:  # 存在开始时间 < t 的课程
            res = min(res, t + pre_dur[l-1])
        
        return res
    
    # 对专业课程也做同样处理
    prof.sort()
    
    prof_suf = [0] * n
    prof_suf[n-1] = prof[n-1][0] + prof[n-1][1]
    for i in range(n-2, -1, -1):
        prof_suf[i] = min(prof_suf[i+1], prof[i][0] + prof[i][1])
    
    prof_pre = [0] * n
    prof_pre[0] = prof[0][1]
    for i in range(1, n):
        prof_pre[i] = min(prof_pre[i-1], prof[i][1])
    
    def query_prof(t):
        l, r = 0, n
        while l < r:
            mid = (l + r) // 2
            if prof[mid][0] >= t:
                r = mid
            else:
                l = mid + 1
        
        res = float('inf')
        if l < n:
            res = min(res, prof_suf[l])
        if l > 0:
            res = min(res, t + prof_pre[l-1])
        
        return res
    
    ans = float('inf')
    
    # 先专业课程后通识课程
    for start, dur in prof:
        end_time = start + dur
        ans = min(ans, query_min(end_time))
    
    # 先通识课程后专业课程
    for start, dur in gen:
        end_time = start + dur
        ans = min(ans, query_prof(end_time))
    
    return ans

print(solve())

• Cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Course {
    int start, dur;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Course> prof(n);
    
    for (int i = 0; i < n; i++) {
        cin >> prof[i].start;
    }
    for (int i = 0; i < n; i++) {
        cin >> prof[i].dur;
    }
    
    int m;
    cin >> m;
    vector<Course> gen(m);
    
    for (int i = 0; i < m; i++) {
        cin >> gen[i].start;
    }
    for (int i = 0; i < m; i++) {
        cin >> gen[i].dur;
    }
    
    // 对通识课程按开始时间排序
    sort(gen.begin(), gen.end(), [](const Course &a, const Course &b) {
        return a.start < b.start;
    });
    
    // 预处理通识课程信息
    vector<ll> gen_suf(m);
    gen_suf[m-1] = gen[m-1].start + gen[m-1].dur;
    for (int i = m-2; i >= 0; i--) {
        gen_suf[i] = min(gen_suf[i+1], (ll)gen[i].start + gen[i].dur);
    }
    
    vector<int> gen_pre(m);
    gen_pre[0] = gen[0].dur;
    for (int i = 1; i < m; i++) {
        gen_pre[i] = min(gen_pre[i-1], gen[i].dur);
    }
    
    auto query_gen = [&](ll t) -> ll {
        int pos = lower_bound(gen.begin(), gen.end(), t, 
                             [](const Course &a, ll val) {
                                 return a.start < val;
                             }) - gen.begin();
        
        ll res = LLONG_MAX;
        if (pos < m) {
            res = min(res, gen_suf[pos]);
        }
        if (pos > 0) {
            res = min(res, t + gen_pre[pos-1]);
        }
        
        return res;
    };
    
    // 对专业课程也做同样处理
    sort(prof.begin(), prof.end(), [](const Course &a, const Course &b) {
        return a.start < b.start;
    });
    
    vector<ll> prof_suf(n);
    prof_suf[n-1] = prof[n-1].start + prof[n-1].dur;
    for (int i = n-2; i >= 0; i--) {
        prof_suf[i] = min(prof_suf[i+1], (ll)prof[i].start + prof[i].dur);
    }
    
    vector<int> prof_pre(n);
    prof_pre[0] = prof[0].dur;
    for (int i = 1; i < n; i++) {
        prof_pre[i] = min(prof_pre[i-1], prof[i].dur);
    }
    
    auto query_prof = [&](ll t) -> ll {
        int pos = lower_bound(prof.begin(), prof.end(), t,
                             [](const Course &a, ll val) {
                                 return a.start < val;
                             }) - prof.begin();
        
        ll res = LLONG_MAX;
        if (pos < n) {
            res = min(res, prof_suf[pos]);
        }
        if (pos > 0) {
            res = min(res, t + prof_pre[pos-1]);
        }
        
        return res;
    };
    
    ll ans = LLONG_MAX;
    
    // 先专业课程后通识课程
    for (const auto& course : prof) {
        ll end_t = course.start + course.dur;
        ans = min(ans, query_gen(end_t));
    }
    
    // 先通识课程后专业课程  
    for (const auto& course : gen) {
        ll end_t = course.start + course.dur;
        ans = min(ans, query_prof(end_t));
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    static class Course {
        int start, dur;
        Course(int s, int d) {
            start = s;
            dur = d;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String[] profStarts = br.readLine().split(" ");
        String[] profDurs = br.readLine().split(" ");
        
        Course[] prof = new Course[n];
        for (int i = 0; i < n; i++) {
            prof[i] = new Course(Integer.parseInt(profStarts[i]), 
                               Integer.parseInt(profDurs[i]));
        }
        
        int m = Integer.parseInt(br.readLine());
        String[] genStarts = br.readLine().split(" ");
        String[] genDurs = br.readLine().split(" ");
        
        Course[] gen = new Course[m];
        for (int i = 0; i < m; i++) {
            gen[i] = new Course(Integer.parseInt(genStarts[i]),
                              Integer.parseInt(genDurs[i]));
        }
        
        // 对通识课程按开始时间排序
        Arrays.sort(gen, (a, b) -> a.start - b.start);
        
        // 预处理通识课程信息
        long[] genSuf = new long[m];
        genSuf[m-1] = gen[m-1].start + gen[m-1].dur;
        for (int i = m-2; i >= 0; i--) {
            genSuf[i] = Math.min(genSuf[i+1], gen[i].start + gen[i].dur);
        }
        
        int[] genPre = new int[m];
        genPre[0] = gen[0].dur;
        for (int i = 1; i < m; i++) {
            genPre[i] = Math.min(genPre[i-1], gen[i].dur);
        }
        
        // 对专业课程也做同样处理
        Arrays.sort(prof, (a, b) -> a.start - b.start);
        
        long[] profSuf = new long[n];
        profSuf[n-1] = prof[n-1].start + prof[n-1].dur;
        for (int i = n-2; i >= 0; i--) {
            profSuf[i] = Math.min(profSuf[i+1], prof[i].start + prof[i].dur);
        }
        
        int[] profPre = new int[n];
        profPre[0] = prof[0].dur;
        for (int i = 1; i < n; i++) {
            profPre[i] = Math.min(profPre[i-1], prof[i].dur);
        }
        
        long ans = Long.MAX_VALUE;
        
        // 先专业课程后通识课程
        for (Course course : prof) {
            long endTime = course.start + course.dur;
            ans = Math.min(ans, queryGen(gen, genSuf, genPre, endTime));
        }
        
        // 先通识课程后专业课程
        for (Course course : gen) {
            long endTime = course.start + course.dur;
            ans = Math.min(ans, queryProf(prof, profSuf, profPre, endTime));
        }
        
        System.out.println(ans);
    }
    
    static long queryGen(Course[] gen, long[] sufMin, int[] preDur, long t) {
        int pos = lowerBound(gen, t);
        long res = Long.MAX_VALUE;
        
        if (pos < gen.length) {
            res = Math.min(res, sufMin[pos]);
        }
        if (pos > 0) {
            res = Math.min(res, t + preDur[pos-1]);
        }
        
        return res;
    }
    
    static long queryProf(Course[] prof, long[] sufMin, int[] preDur, long t) {
        int pos = lowerBound(prof, t);
        long res = Long.MAX_VALUE;
        
        if (pos < prof.length) {
            res = Math.min(res, sufMin[pos]);
        }
        if (pos > 0) {
            res = Math.min(res, t + preDur[pos-1]);
        }
        
        return res;
    }
    
    static int lowerBound(Course[] arr, long target) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid].start >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

02. 智慧农场灌溉系统

问题描述

小基管理着一个 的智慧农场，农场被划分成网格状的地块。初始时，所有地块都没有安装自动灌溉设备。为了提高农作物产量，小基可以执行任意次设备安装操作：选择任意一列，对第 列中从上到下的所有地块安装自动灌溉设备，该列的所有地块将被标记为"已安装灌溉设备"状态。

在安装灌溉设备后，对于处于"未安装灌溉设备"状态的地块 ，如果其左侧或右侧相邻地块中至少有一个处于"已安装灌溉设备"