✅ 春招备战指南 ✅

💡 学习建议：

先尝试独立解题（建议用时：90分钟/套）

对照解析查漏补缺

配套练习题库

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

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

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

题目总结

题目一：登山计划优化

1️⃣：计算相邻特定日期之间的间隔成本

2️⃣：对间隔成本排序，优先合并成本低的区间

3️⃣：贪心选择尽可能多的区间合并，计算最终移动次数

难度：中等

这道题目考察贪心算法的应用。关键在于理解问题可以转化为区间合并问题，并且应该优先合并间隔小的相邻特定日期，以最大化合并区间的数量。通过排序和贪心选择，可以在 O(n log n) 的时间复杂度内解决问题。

题目二：汽车采购方案优化

1️⃣：将每种汽车的每种配置方案视为独立物品

2️⃣：构建二维完全背包DP模型

3️⃣：状态转移求解最小采购成本

难度：中等偏难

这道题目是二维完全背包问题的变种，需要同时满足载人和载货两个约束条件，目标是最小化总成本。关键在于正确构建状态转移方程，并处理好边界条件。时间复杂度为 O(X×Y×(n+∑k_i))，其中 X 和 Y 分别是载人和载货需求，n 是汽车型号数量，∑k_i 是所有选配方案的总数。

01. 登山计划优化

问题描述

小毛是一位热爱极限挑战的登山爱好者，他计划挑战世界最高峰——珠穆朗玛峰。由于珠峰气候多变，小毛通过特殊渠道获知了未来有 天可能是适合登顶的好天气。

珠峰大本营位于海拔 米处，长期停留对健康有严重影响。根据医生评估，小毛最多只能在大本营停留总共 天，否则将面临严重的健康风险。

每次从低海拔地区前往大本营或从大本营返回低海拔地区都需要花费大量体力和资源，被视为一次"移动"。小毛希望在不错过任何一个可能的登顶好天气的前提下，尽可能减少移动次数。

请注意，小毛一开始位于低海拔地区，最终也必须返回低海拔地区。一次移动指的是单程而非往返，即从低海拔地区前往珠峰大本营或从珠峰大本营下撤回低海拔地区分别算作一次移动。

输入格式

第一行包含两个正整数 和 ，分别表示可能适合登顶的天数和小毛最多能在大本营停留的总天数，保证 。

第二行包含 个递增的正整数 ，其中 表示第 个可能适合登顶的日子是从计划开始后的第 天。

输出格式

输出一个整数，表示小毛在满足所有条件下需要的最少移动次数。

样例输入

5 8

2 3 5 6 10

样例输出

4

样例 解释说明

样例1

小毛需要在第2、3、5、6、10天都待在大本营，共5天。由于他最多可以停留8天，所以可以将第2、3天和第5、6天分别合并为两个连续的停留区间，第10天单独作为一个区间。这样共有3个停留区间，每个区间需要上山和下山各一次，总共需要6次移动。但实际上，小毛可以将第2、3、5、6天合并为一个连续的停留区间（停留第2-6天，共5天），第10天单独作为一个区间，这样只有2个停留区间，总共需要4次移动。

数据范围

题解

这道题目要求在满足两个条件的前提下，最小化移动次数：

必须在所有 个特定日期都待在大本营

在大本营的总停留天数不能超过 天

首先，我们需要理解一个关键点：每次从低海拔到大本营再返回低海拔，算作两次移动。因此，我们的目标是尽可能减少上山下山的次数，也就是减少停留区间的数量。

最直接的思路是将相邻的特定日期合并成连续的停留区间。例如，如果第 天和第 天都需要在大本营，那么从第 天到第 天都待在大本营会更有效率。但这样做会增加额外的停留天数，即 天。

我们可以定义这个额外天数为"间隔成本"（gap cost）。如果我们有足够的额外停留天数预算（即 天），那么我们应该优先合并那些间隔成本较小的相邻特定日期。

具体算法如下：

计算所有相邻特定日期之间的间隔成本：

将这些间隔成本从小到大排序

从最小的间隔成本开始，尽可能多地合并相邻特定日期，直到用完额外停留天数预算

计算最终的停留区间数量，每个区间需要2次移动（上山和下山）

时间复杂度：，主要是排序的时间复杂度。 空间复杂度：，用于存储间隔成本数组。

这个贪心算法之所以有效，是因为我们总是优先选择合并成本最低的相邻日期，这样可以用有限的额外停留天数预算合并尽可能多的区间，从而最小化移动次数。

参考代码

Python

import sys

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

# 读取输入

n, k = map(int, input().split())

days = list(map(int, input().split()))

# 计算相邻特定日期之间的间隔成本

gaps = []

for i in range(n - 1):

# 间隔成本 = 下一个特定日期 - 当前特定日期 - 1

gaps.append(days[i+1] - days[i] - 1)

# 对间隔成本进行排序，优先合并成本低的

gaps.sort()

# 计算可用于填补间隔的额外天数

extra_days = k - n

# 尝试合并尽可能多的区间

merged_count = 0

for gap in gaps:

# 如果当前间隔成本可以被额外天数覆盖

if gap <= extra_days:

extra_days -= gap # 减少可用额外天数

merged_count += 1 # 增加合并次数

else:

# 如果当前间隔成本太大，无法合并，则跳出循环

break

# 计算最终的区间数量和移动次数

# 初始有n个区间，每合并一次减少一个区间

# 每个区间需要2次移动（上山和下山）

total_moves = 2 * (n - merged_count)

print(total_moves)

Cpp

#include

#include

#include

using namespace std;

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

// 读取输入

int n, k;

cin >> n >> k;

vector days(n);

for (int i = 0; i < n; i++) {

cin >> days[i];

}

// 计算相邻特定日期之间的间隔成本

vector gaps;

for (int i = 0; i < n - 1; i++) {

// 间隔成本 = 下一个特定日期 - 当前特定日期 - 1

gaps.push_back(days[i+1] - days[i] - 1);

}

// 对间隔成本进行排序，优先合并成本低的

sort(gaps.begin(), gaps.end());

// 计算可用于填补间隔的额外天数

int extra_days = k - n;

// 尝试合并尽可能多的区间

int merged_count = 0;

for (int gap : gaps) {

// 如果当前间隔成本可以被额外天数覆盖

if (gap <= extra_days) {

extra_days -= gap; // 减少可用额外天数

merged_count++; // 增加合并次数

} else {

// 如果当前间隔成本太大，无法合并，则跳出循环

break;

}

}

// 计算最终的区间数量和移动次数

// 初始有n个区间，每合并一次减少一个区间

// 每个区间需要2次移动（上山和下山）

int total_moves = 2 * (n - merged_count);

cout << total_moves << "\n";

return 0;

}

Java

import java.util.Arrays;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

// 读取输入

int n = sc.nextInt(); // 特定日期的数量

int k = sc.nextInt(); // 最大停留天数

int[] days = new int[n];

for (int i = 0; i < n; i++) {

days[i] = sc.nextInt();

}

// 计算相邻特定日期之间的间隔成本

int[] gaps = new int[n - 1];

for (int i = 0; i < n - 1; i++) {

// 间隔成本 = 下一个特定日期 - 当前特定日期 - 1

gaps[i] = days[i+1] - days[i] - 1;

}

// 对间隔成本进行排序，优先合并成本低的

Arrays.sort(gaps);

// 计算可用于填补间隔的额外天数

int extraDays = k - n;

// 尝试合并尽可能多的区间

int mergedCount = 0;

for (int gap : gaps) {

// 如果当前间隔成本可以被额外天数覆盖

if (gap <= extraDays) {

extraDays -= gap; // 减少可用额外天数

mergedCount++; // 增加合并次数

} else {

// 如果当前间隔成本太大，无法合并，则跳出循环

break;

}

}

// 计算最终的区间数量和移动次数

// 初始有n个区间，每合并一次减少一个区间

// 每个区间需要2次移动（上山和下山）

int totalMoves =