✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

携程

题目一：小兰的温度计校准

1️⃣：对给定读数进行区间分类判断

2️⃣：按照固定顺序输出所有匹配的类型标识

难度：简单

这道题目是经典的区间分类问题。需要判断温度读数是否落在三种温度计的有效范围内，由于区间存在重叠，需要按顺序检查所有区间。通过简单的条件判断即可在 O(1) 时间内完成分类，总体复杂度 O(T)。

题目二：小毛的卡牌收集

1️⃣：维护数组前缀的最大值

2️⃣：利用贪心思想计算最少补全数量

难度：中等

这道题目的关键在于理解如何构造最小的连续编号集合。对于长度为 i 的前缀，其最大值为 mx，要构造连续集合的最小规模是 max(i, mx)，因此需要补全 max(0, mx - i) 个元素。通过维护前缀最大值，可以在 O(n) 时间内解决问题。

题目三：小基的班次排班

1️⃣：利用数论知识分析模运算规律

2️⃣：使用前缀和思想计算区间内满足条件的数量

难度：中等

这道题目是经典的模运算计数问题。通过分析满足 i % k = x 的数构成的等差数列规律，可以推导出计算公式。利用前缀和思想，将区间 [l,r] 的查询转化为 f(r) - f(l-1)，其中 f(n) 表示 [1,n] 中满足条件的数的个数。

题目四：小柯的物流网络优化

1️⃣：使用多源 Dijkstra 算法处理树上最短路

2️⃣：为每个节点维护优先队列存储前 K 小距离

3️⃣：通过剪枝优化提高算法效率

难度：困难

这道题目结合了图论算法和数据结构的综合应用。核心思想是将所有配送中心作为源点进行多源最短路搜索，同时为每个城市维护一个大小不超过 K 的最大堆来存储前 K 小的距离。通过合理的剪枝策略，可以在 O((n+m)log n + nK log K) 时间内完成计算。

01. 小兰的温度计校准

问题描述

小兰在实验室里负责温度计的校准工作。实验室有三种不同类型的温度计，它们各自的有效测量范围如下（单位：摄氏度）：

• 高精度温度计：
• 标准温度计：
• 工业温度计：

现在小兰需要对一批待校准的温度计进行分类。给定某个温度计的读数 ，请判断这个温度计可能属于以上哪几种类型。由于测量范围存在重叠，一个读数可能同时符合多种温度计的规格；如果不属于任何一类，则认为是"未知类型"。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 （）表示数据组数。

每组测试数据描述如下：每行输入一个整数 （）表示当前温度计的读数（单位：摄氏度）。

输出格式

对每组测试数据，新起一行输出该温度计可能的类型；若同时属于多类，则按以下固定顺序以单个空格分隔输出全部命中的类别：高精度温度计，输出 G；标准温度计，输出 D；工业温度计，输出 C。若不属于任意一类，则输出 other。区间两端点均计入（闭区间）。

样例输入

6
250
170
120
300
351
200

样例输出

G D C
D
other
G C
other
D C

样例	解释说明
样例1	读数250同时在三种温度计的有效范围内，输出G D C
样例2	读数170只在标准温度计范围内，输出D
样例3	读数120不在任何温度计范围内，输出other
样例4	读数300在高精度和工业温度计范围内，输出G C
样例5	读数351超出所有温度计范围，输出other
样例6	读数200在标准和工业温度计范围内，输出D C

数据范围

• 
• 

题解

这道题目的本质是区间判断问题。对于给定的温度读数，需要判断它是否落在各个温度计的有效范围内。

核心思路很简单：对于每个输入的温度值，依次检查它是否在各个区间内：

• 高精度温度计（G）：
• 标准温度计（D）：
• 工业温度计（C）：

由于区间存在重叠，一个温度值可能同时属于多个类型。比如温度250既在高精度温度计范围内，也在标准温度计和工业温度计范围内。

算法步骤：

1. 读取温度值
2. 按照题目要求的顺序（G D C）依次检查 是否在对应区间内
3. 如果在某个区间内，就将对应的字母加入结果
4. 如果所有区间都不满足，输出"other"

时间复杂度：每次查询 ，总体复杂度 。

参考代码

Python

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

t = int(input())
for _ in range(t):
    v = int(input())
    res = []
    
    # 检查高精度温度计范围 [250, 350]
    if 250 <= v <= 350:
        res.append('G')
    
    # 检查标准温度计范围 [160, 250]
    if 160 <= v <= 250:
        res.append('D')
    
    # 检查工业温度计范围 [200, 300]
    if 200 <= v <= 300:
        res.append('C')
    
    # 输出结果
    if res:
        print(' '.join(res))
    else:
        print('other')

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int v;
        cin >> v;
        
        vector<string> types;
        
        // 检查高精度温度计范围 [250, 350]
        if (v >= 250 && v <= 350) {
            types.push_back("G");
        }
        
        // 检查标准温度计范围 [160, 250]
        if (v >= 160 && v <= 250) {
            types.push_back("D");
        }
        
        // 检查工业温度计范围 [200, 300]
        if (v >= 200 && v <= 300) {
            types.push_back("C");
        }
        
        // 输出结果
        if (!types.empty()) {
            for (int i = 0; i < types.size(); i++) {
                if (i > 0) cout << " ";
                cout << types[i];
            }
            cout << "\n";
        } else {
            cout << "other\n";
        }
    }
    
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int v = sc.nextInt();
            List<String> types = new ArrayList<>();
            
            // 检查高精度温度计范围 [250, 350]
            if (v >= 250 && v <= 350) {
                types.add("G");
            }
            
            // 检查标准温度计范围 [160, 250]
            if (v >= 160 && v <= 250) {
                types.add("D");
            }
            
            // 检查工业温度计范围 [200, 300]
            if (v >= 200 && v <= 300) {
                types.add("C");
            }
            
            // 输出结果
            if (!types.isEmpty()) {
                System.out.println(String.join(" ", types));
            } else {
                System.out.println("other");
            }
        }
        
        sc.close();
    }
}

02. 小毛的卡牌收集

问题描述

小毛是一位热心的卡牌收集爱好者。他收集的是一套编号从 开始连续编号的特殊卡牌系列。由于各种原因，小毛目前手中的卡牌并不完整，只有长度为 的序列 。

小毛想要了解自己收集的进度。对于每个位置 （），他想知道：如果只考虑前 张卡牌 ，要让这些卡牌组成一个完整的连续编号集合（即 的形式），最少还需要收集多少张卡牌？

为了使需要收集的卡牌数量最少，小毛会选择最优的集合大小 。注意， 必须不小于当前已有卡牌中的最大编号。

请输出每个前缀所需收集的最少卡牌数。

【名词解释】

连续编号集合：由 这 个整数组成的集合，每个整数恰好出现一次。例如， 是一个大小为 5 的连续编号集合，而 和 都不是连续编号集合，因为前者存在重复元素，后者不连续。

输入格式

第一行输入一个整数 （），表示小毛当前拥有的卡牌数量。

第二行输入 个整数 （），表示小毛拥有的卡牌编号。

输出格式

在一行上输出 个整数，用空格分隔。其中第 个整数表示前缀 需要收集的最少卡牌数。

样例输入

3
3 1 6

5
1 2 3 4 5

样例输出

2 1 3

0 0 0 0 0

样例	解释说明
样例1	前缀{3}需要收集{1,2}共2张；前缀{3,1}需要收集{2}共1张；前缀{3,1,6}需要收集{2,4,5}共3张
样例2	每个前缀都已经是完整的连续编号集合，无需收集额外卡牌

数据范围

• 
• 

题解

这道题目的核心是理解如何构造最小的连续编号集合。

对于前缀 ，假设其中的最大值为 。要构造一个包含这些卡牌的连续编号集合，集合的大小 必须满足：

1. （因为集合必须包含最大的卡牌编号）
2. （因为集合至少要能容纳前缀中已有的 张卡牌）

为了使需要收集的卡牌数量最少，应该选择 。

此时需要收集的卡牌数量为：

算法思路：

1. 遍历数组，维护当前前缀的最大值
2. 对于第 个位置，计算 作为答案
3. 时间复杂度 ，空间复杂度

举个例子：前缀 ，最大值是 3，长度是 2。要构造连续集合，最小需要 ，已经有 ，所以还需要收集 1 张卡牌（编号2）。

参考代码

Python

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

n = int(input())
arr = list(map(int, input().split()))

mx = 0  # 当前前缀的最大值
res = []

for i in range(n):
    mx = max(mx, arr[i])  # 更新前缀最大值
    need = max(0, mx - (i + 1))  # 计算需要收集的卡牌数
    res.append(need)

print(' '.join(map(str, res)))

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    long long mx = 0;  // 当前前缀的最大值
    
    for (int i = 1; i <= n; i++) {
        long long a;
        cin >> a;
        
        mx = max(mx, a);  // 更新前缀最大值
        long long need = max(0LL, mx - i);  // 计算需要收集的卡牌数
        
        if (i > 1) cout << " ";
        cout << need;
    }
    cout << "\n";
    
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long maxVal = 0;  // 当前前缀的最大值
        List<Long> result = new ArrayList<>();
        
        for (int i = 1; i <= n; i++) {
            long a = sc.nextLong();
            maxVal = Math.max(maxVal, a);  // 更新前缀最大值
            long need = Math.max(0L, maxVal - i);  // 计算需要收集的卡牌数
            result.add(need);
        }
        
        // 输出结果
        for (int i = 0; i < result.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(result.get(i));
        }