✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

题目一：最优删除策略

1️⃣：对数据集进行排序，找出最大值、次大值、最小值和次小值

2️⃣：比较删除最大值和删除最小值两种策略，取较小的波动值

难度：中等

这道题目的关键在于观察到波动值只与最大值和最小值有关，因此最优策略一定是删除最大值或最小值。通过排序后比较两种策略，可以在 O(n log n) 的时间复杂度内解决问题。

题目二：分形艺术画布

1️⃣：计算初始黑色面积（第一阶段）

2️⃣：根据奇偶性交替增减黑色面积

3️⃣：利用几何规律计算每个阶段的圆半径

难度：中等

这道题目需要理解分形的递归特性，并发现每次新绘制的圆半径是前一个圆半径的一半。通过模拟每个阶段的面积变化，可以在 O(n) 的时间复杂度内计算最终的黑色面积。

题目三：智能物流配送系统

1️⃣：创建超级源点连接所有配送中心

2️⃣：使用Dijkstra算法计算从超级源点到所有城市的最短路径

3️⃣：对每个查询直接返回对应城市的最短路径值

难度：中等偏难

这道题目考察了图论中的最短路径算法，关键技巧是使用"超级源点"将多源最短路问题转化为单源最短路问题。通过一次Dijkstra算法，可以在 O((n+m) log n) 的时间复杂度内解决所有查询。

01. 最优删除策略

问题描述

小柯是一位数据分析师，她正在研究一组数据的波动范围。对于一个数据集，她定义其"波动值"为数据集中最大值与最小值的差。

为了使数据更加稳定，小柯可以从数据集中删除一个元素。她想知道，通过最优的删除策略，能够得到的最小波动值是多少。

输入格式

第一行输入一个整数 ，表示测试用例的数量。

对于每组测试用例：

• 第一行输入一个整数 ，表示数据集的大小。
• 第二行输入 个整数，表示数据集中的各个元素。

输出格式

对于每组测试用例，输出一个整数，表示删除一个元素后能够得到的最小波动值。

样例输入

1
4
1 3 3 7

样例输出

2

样例 解释说明

样例1	原始数据集为 [1,3,3,7]，如果删除元素 7，剩余数据集为 [1,3,3]，此时波动值为 3-1=2。如果删除其他任何元素，得到的波动值都不会更小。

数据范围

• 
• 
• 

题解

这道题目看似简单，但其中蕴含着一个重要的观察：要使波动值最小，我们应该考虑删除最大值或最小值。

为什么呢？因为波动值只与最大值和最小值有关，删除中间的元素不会改变波动值，除非这个元素恰好是唯一的最大值或最小值。

具体来说，我们有两种选择：

1. 删除最大值：此时新的波动值为"次大值-最小值"
2. 删除最小值：此时新的波动值为"最大值-次小值"

我们只需要计算这两种情况，并取较小的那个作为答案。

实现上，我们可以先对数组进行排序，这样最小值在索引0，次小值在索引1，次大值在索引n-2，最大值在索引n-1。然后比较"次大值-最小值"和"最大值-次小值"，取较小值即可。

时间复杂度分析：排序的时间复杂度为 ，其他操作的时间复杂度为 ，因此总时间复杂度为 ，对于给定的数据范围（）是完全可接受的。

参考代码

• Python

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

def solve():
    # 读取测试用例数量
    t = int(input())
    
    for _ in range(t):
        # 读取数据集大小
        n = int(input())
        # 读取数据集
        nums = list(map(int, input().split()))
        
        # 对数据集排序
        nums.sort()
        
        # 计算两种情况：删除最大值或删除最小值
        opt1 = nums[n-2] - nums[0]    # 删除最大值
        opt2 = nums[n-1] - nums[1]    # 删除最小值
        
        # 输出较小的波动值
        print(min(opt1, opt2))

if __name__ == "__main__":
    solve()

• Cpp

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

void solve() {
    // 读取测试用例数量
    int t;
    cin >> t;
    
    while (t--) {
        // 读取数据集大小
        int n;
        cin >> n;
        
        // 读取数据集
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 对数据集排序
        sort(a.begin(), a.end());
        
        // 计算两种情况：删除最大值或删除最小值
        int opt1 = a[n-2] - a[0];    // 删除最大值
        int opt2 = a[n-1] - a[1];    // 删除最小值
        
        // 输出较小的波动值
        cout << min(opt1, opt2) << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        
        for (int tc = 0; tc < t; tc++) {
            // 读取数据集大小
            int n = Integer.parseInt(br.readLine().trim());
            
            // 读取数据集
            String[] line = br.readLine().trim().split(" ");
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(line[i]);
            }
            
            // 对数据集排序
            Arrays.sort(nums);
            
            // 计算两种情况：删除最大值或删除最小值
            int opt1 = nums[n-2] - nums[0];    // 删除最大值
            int opt2 = nums[n-1] - nums[1];    // 删除最小值
            
            // 输出较小的波动值
            System.out.println(Math.min(opt1, opt2));
        }
    }
}

02. 分形艺术画布

问题描述

小基是一位数字艺术家，她正在创作一系列基于几何分形的艺术作品。她的创作过程如下：

第一阶段：她在画布上绘制一个半径为 的圆，并将左上部分的四分之一区域切除，保留剩余的四分之三圆形区域，并将其涂成黑色。

第二阶段：在第一阶段的黑色区域内，她绘制一个尽可能大的圆，并将右下部分的四分之一区域切除，将这个新的四分之三圆形区域涂成白色。

第三阶段：在第二阶段新增的白色区域内，她绘制一个尽可能大的圆，并将左上部分的四分之一区域切除，将这个新的四分之三圆形区域涂成黑色。

以此类推，每个阶段都在前一阶段新增的区域内绘制尽可能大的圆，切除特定的四分之一区域，并交替使用黑色和白色进行涂色。

现在，小基想知道在完成第 阶段后，画布上黑色区域的总面积是多少。

输入格式

输入包含两个正整数 和 ，分别表示初始圆的半径和创作的阶段数。

输出格式

输出一个实数，表示第 阶段完成后黑色区域的总面积。如果你的答案与标准答案的绝对误差或相对误差不超过 ，则被视为正确。

样例输入

1 1

样例输出

2.3561945

样例输入

2 4

样例输出

7.5103699

样例 解释说明

样例1	第一阶段：绘制半径为1的圆，切除左上四分之一，黑色面积为
样例2	第四阶段完成后，黑色区域的总面积约为7.5103699（详见图示）

数据范围

• 
• 

题解

这道题目描述了一个有趣的几何分形过程，我们需要计算最终的黑色区域面积。

首先，让我们分析一下这个过程：

1. 第一阶段：黑色区域是一个四分之三圆，面积为
2. 第二阶段：在黑色区域内绘制一个白色的四分之三圆，这个新圆的半径是多少？

观察可知，每次新绘制的圆的半径是前一个圆半径的一半。这是因为当我们在一个圆内绘制尽可能大的圆时，新圆的直径等于原圆的半径。

另外，我们注意到奇数阶段（第1、3、5...阶段）会增加黑色面积，而偶数阶段（第2、4、6...阶段）会减少黑色面积。

因此，我们可以用以下公式计算第n阶段后的黑色面积：

• 初始黑色面积 =
• 对于i从2到n的每个阶段：
  • 如果i是偶数，减去
  • 如果i是奇数，加上

这个公式可以简化为一个等比数列求和问题。但为了直观理解，我们可以直接模拟这个过程，逐阶段计算面积变化。

时间复杂度分析：算法的时间复杂度为 ，其中n是阶段数。由于n最大为30，这个复杂度是完全可以接受的。

参考代码

• Python

import sys
import math

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

def solve():
    # 读取初始半径和阶段数
    r, n = map(float, input().split())
    
    # 计算初始黑色面积（第一阶段）
    pi = math.pi
    area = pi * r * r * 0.75
    
    # 模拟后续阶段
    for i in range(2, int(n) + 1):
        # 计算当前阶段圆的半径
        r = r / 2
        # 计算当前阶段圆的面积
        curr_area = pi * r * r * 0.75
        
        # 奇数阶段增加黑色面积，偶数阶段减少黑色面积
        if i % 2 == 0:
            area -= curr_area
        else:
            area += curr_area
    
    # 输出结果，保留7位小数
    print(f"{area:.7f}")

if __name__ == "__main__":
    solve()

• Cpp

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

void solve() {
    // 读取初始半径和阶段数
    double r;
    int n;