✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魔法水晶的光芒测量

1️⃣：使用多源最短路算法，以所有水晶位置为起点进行BFS扩展

2️⃣：利用优先队列保证按光芒强度从小到大处理位置

3️⃣：向左右相邻位置扩展，直到输出K个最小值

难度：中等

这道题目的关键在于理解问题本质是一维数轴上的多源最短路问题。通过将所有魔法水晶作为起点，使用优先队列进行类似BFS的扩展，可以保证按光芒强度从小到大的顺序输出结果，实现O((N+K)log(N+K))的高效解法。

题目二：赛车引擎优化计算

1️⃣：建立两个引擎系统到达时间的数学模型

2️⃣：通过不等式变形推导出最大推力值的计算公式

3️⃣：使用高精度数据类型避免乘法溢出

难度：简单

这道题目是一个典型的数学推导问题，需要根据两个引擎系统的特性建立时间函数，然后通过不等式求解得到最大推力值的公式。关键在于理解物理意义并正确处理大数乘法可能产生的溢出问题。

01. 魔法水晶的光芒测量

问题描述

小兰是一位资深的魔法研究员，专门研究古代遗迹中的神秘水晶。在最新发现的地下洞穴中，她发现了一个奇特的现象：沿着洞穴的主通道，分布着 颗会发光的魔法水晶。

这些魔法水晶按照从左到右的顺序，分别位于通道上的 位置处，且满足 。

小兰需要测量通道上每个位置的"光芒强度"。根据她的研究，任意位置 的光芒强度定义为该位置到最近魔法水晶的距离，即：

为了完成她的魔法实验，小兰需要找出从位置 到位置 （共 个整数位置）中，光芒强度最小的 个值，并按照从小到大的顺序记录下来。

输入格式

第一行包含三个正整数 ，分别表示通道的长度、魔法水晶的数量以及需要找出的最小光芒强度值的个数。

第二行包含 个正整数 ，表示每颗魔法水晶在通道上的位置。

输出格式

输出 行，每行一个整数，表示按从小到大排序后的第 小光芒强度值。

样例输入

10 3 5
1 4 8

样例输出

0
0
0
1
1

数据范围

题解

这道题的核心思想是使用多源最短路算法来解决。

首先分析问题本质：我们需要找到所有位置中光芒强度（到最近水晶的距离）最小的 个值。这实际上是一个在一维数轴上的多源最短路问题。

解法思路：

1. 将所有魔法水晶的位置作为起始点，它们的光芒强度都是0
2. 使用优先队列（小根堆）进行类似BFS的扩展
3. 每次取出当前光芒强度最小的位置，记录这个强度值
4. 向左右两个相邻位置扩展，如果这些位置在有效范围内且未被访问过，就加入队列
5. 重复上述过程，直到输出了 个值

关键观察：由于一维数轴上相邻位置的距离为1，使用优先队列可以保证按光芒强度从小到大的顺序处理位置，因此输出的序列天然有序。

时间复杂度：，其中需要处理的位置数最多为 。

空间复杂度：，用于存储队列和访问标记。

参考代码

• Python

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

import heapq

# 读取输入
L, N, K = map(int, input().split())
crystals = list(map(int, input().split()))

# 初始化访问集合和优先队列
visited = set(crystals)
pq = [(0, pos) for pos in crystals]  # (光芒强度, 位置)
heapq.heapify(pq)

count = 0
while count < K and pq:
    # 取出当前光芒强度最小的位置
    strength, pos = heapq.heappop(pq)
    print(strength)
    count += 1
    
    # 向左右扩展
    for next_pos in [pos - 1, pos + 1]:
        # 检查位置是否有效且未访问
        if 0 <= next_pos <= L and next_pos not in visited:
            visited.add(next_pos)
            heapq.heappush(pq, (strength + 1, next_pos))

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long L;
    int N, K;
    cin >> L >> N >> K;
    
    vector<long long> crystals(N);
    for (int i = 0; i < N; i++) {
        cin >> crystals[i];
    }
    
    // 优先队列存储 (光芒强度, 位置)
    priority_queue<pair<long long, long long>, 
                   vector<pair<long long, long long>>, 
                   greater<pair<long long, long long>>> pq;
    
    unordered_set<long long> visited;
    
    // 初始化所有水晶位置
    for (long long pos : crystals) {
        pq.push({0, pos});
        visited.insert(pos);
    }
    
    int count = 0;
    while (count < K && !pq.empty()) {
        auto [strength, pos] = pq.top();
        pq.pop();
        
        cout << strength << "\n