前端区块链开发_免费b站推广网站mmm_网站检测中心_子域名网址查询

题目总结

题目一：登山计划优化

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

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

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

难度：中等

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

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

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

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

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

难度：中等偏难

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

01. 登山计划优化

问题描述

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

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

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

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

输入格式

第一行包含两个正整数 $n$ 和 $k$，分别表示可能适合登顶的天数和A先生最多能在大本营停留的总天数，保证 $n\le k$。

第二行包含 $n$ 个递增的正整数 $a_1,a_2,\dots ,a_n$，其中 $a_i$ 表示第 $i$ 个可能适合登顶的日子是从计划开始后的第 $a_i$ 天。

输出格式

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

样例输入

5 8
2 3 5 6 10

样例输出

4

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

数据范围

• $1\le n,k,a_i\le 10^5$
• $a_1<a_2<\dots <a_n$

题解

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

1. 必须在所有 $n$ 个特定日期都待在大本营
2. 在大本营的总停留天数不能超过 $k$ 天

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

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

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

具体算法如下：

1. 计算所有相邻特定日期之间的间隔成本：$ga{p}_i=a_{i+1}-a_i-1$
2. 将这些间隔成本从小到大排序
3. 从最小的间隔成本开始，尽可能多地合并相邻特定日期，直到用完额外停留天数预算
4. 计算最终的停留区间数量，每个区间需要2次移动（上山和下山）

时间复杂度：$O(n\log n)$，主要是排序的时间复杂度。
空间复杂度：$O(n)$，用于存储间隔成本数组。

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

参考代码

• 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):# 间隔成本 = 下一个特定日期 - 当前特定日期 - 1gaps.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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// 读取输入int n, k;cin >> n >> k;vector<int> days(n);for (int i = 0; i < n; i++) {cin >> days[i];}// 计算相邻特定日期之间的间隔成本vector<int> gaps;for (int i = 0; i < n - 1; i++) {// 间隔成本 = 下一个特定日期 - 当前特定日期 - 1gaps.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++) {// 间隔成本 = 下一个特定日期 - 当前特定日期 - 1gaps[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 = 2 * (n - mergedCount);System.out.println(totalMoves);sc.close();}
}

---

02. 汽车采购方案优化

问题描述

卢小姐是一家物流公司的采购经理，她需要为公司采购一批汽车，以满足公司的运营需求。公司要求这批汽车总共能够载运至少 $X$ 人，并且能够承载至少 $Y$ 立方米的货物。

市场上有 $n$ 种不同型号的汽车可供选择。每种汽车都有一个默认配置方案，同时还可能提供若干种选配方案。对于第 $i$ 种汽车，其默认配置的价格为 $m_i$ 元，载人能力为 $x_i$ 人，载货能力为 $y_i$ 立方米。此外，该型号还有 $k_i$ 种选配方案，第 $j$ 种选配方案会使价格变化 $m_{ij}$ 元（可能增加也可能减少），载人能力变化 $x_{ij}$ 人，载货能力变化 $y_{ij}$ 立方米。

卢小姐可以采购任意数量、任意型号的汽车，每辆汽车只能选择一种配置方案（默认方案或某一种选配方案）。她希望在满足公司需求的前提下，最小化总采购成本。

输入格式

第一行包含三个正整数 $X$、$Y$ 和 $n$，分别表示载人需求、载货需求（立方米）和汽车型号数量。

接下来是 $n$ 组数据，每组数据描述一种汽车型号：

• 第一行包含四个整数 $m_i$、$x_i$、$y_i$ 和 $k_i$，分别表示默认配置的价格、载人能力、载货能力和选配方案数量。
• 接下来 $k_i$ 行，每行包含三个整数 $m_{ij}$、$x_{ij}$ 和 $y_{ij}$，分别表示第 $j$ 种选配方案的价格变化、载人能力变化和载货能力变化。

输出格式

输出一个整数，表示满足需求的最小总采购成本。

样例输入

10 20 2
100 2 6 1
20 1 1
80 5 1 1
10 -1 2

样例输出

390

样例	解释说明
样例1	有两种汽车型号。第一种默认配置价格100元，载人2人，载货6立方米，有1种选配方案：价格增加20元，载人增加1人，载货增加1立方米。第二种默认配置价格80元，载人5人，载货1立方米，有1种选配方案：价格增加10元，载人减少1人，载货增加2立方米。最优方案是购买3辆第一种汽车的选配版（每辆价格120元，载人3人，载货7立方米）和1辆第二种汽车的选配版（价格90元，载人4人，载货3立方米），总价为3×120+90=450元，总载人能力为3×3+4=13人，总载货能力为3×7+3=24立方米，满足需求。

数据范围

• $1\le X,Y,n\le 200$
• $1\le m_i,x_i,y_i\le 10^5$
• $0\le k_i\le 10^5$
• $-10^5\le m_{ij},x_{ij},y_{ij}\le 10^5$
• 所有选配后的价格、载人能力和载货能力均为正整数
• 所有 $k_i$ 的总和不超过 $200-n$

题解

这道题目是一个典型的二维背包问题的变种。我们需要在满足两个约束条件（载人能力和载货能力）的前提下，最小化总成本。

与传统背包问题不同的是，这里的"物品"是可以无限次选择的（即可以购买任意数量的汽车），因此是一个二维的完全背包问题。

首先，我们需要将每种汽车的每种配置方案视为一个独立的"物品"。对于第 $i$ 种汽车的第 $j$ 种选配方案，其属性为：

• 成本：$cos{t}_{ij}=m_i+m_{ij}$
• 载人能力：$perso{n}_{ij}=x_i+x_{ij}$
• 载货能力：$carg{o}_{ij}=y_i+y_{ij}$

其中，默认配置可以看作是一种特殊的选配方案，其 $m_{ij}=x_{ij}=y_{ij}=0$。

接下来，我们定义状态 $dp[i][j]$ 表示载人能力至少为 $i$ 且载货能力至少为 $j$ 时的最小成本。初始状态 $dp[0][0]=0$，其他状态初始化为无穷大。

状态转移方程为：
$dp[min(i+perso{n}_{ij},X)][min(j+carg{o}_{ij},Y)]=min(dp[min(i+perso{n}_{ij},X)][min(j+carg{o}_{ij},Y)],dp[i][j]+cos{t}_{ij})$

这个方程的含义是：如果我们已经达到了载人能力 $i$ 和载货能力 $j$，那么通过购买一辆配置为 $(perso{n}_{ij},carg{o}_{ij})$ 的汽车，我们可以达到载人能力 $i+perso{n}_{ij}$ 和载货能力 $j+carg{o}_{ij}$，成本增加 $cos{t}_{ij}$。由于我们只关心达到或超过 $X$ 和 $Y$ 的情况，所以取 $min(i+perso{n}_{ij},X)$ 和 $min(j+carg{o}_{ij},Y)$。

最终答案为 $dp[X][Y]$，即达到载人能力至少为 $X$ 且载货能力至少为 $Y$ 时的最小成本。

时间复杂度：$O(X\times Y\times (n+\sum k_i))$，其中 $n$ 是汽车型号数量，$\sum k_i$ 是所有选配方案的总数。
空间复杂度：$O(X\times Y)$，用于存储动态规划数组。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()def min_cost_for_car_purchase():# 读取输入X, Y, n = map(int, input().split())# 存储所有汽车配置方案options = []# 处理每种汽车型号for _ in range(n):m, x, y, k = map(int, input().split())# 添加默认配置options.append((m, x, y))# 添加选配方案for _ in range(k):m_add, x_add, y_add = map(int, input().split())options.append((m + m_add, x + x_add, y + y_add))# 初始化dp数组，dp[i][j]表示载人i人、载货j立方米的最小成本INF = float('inf')dp = [[INF] * (Y + 1) for _ in range(X + 1)]dp[0][0] = 0  # 基础情况：不需要载人载货时成本为0# 动态规划求解for i in range(X + 1):for j in range(Y + 1):if dp[i][j] == INF:continue# 尝试每种配置方案for cost, person, cargo in options:# 更新状态new_i = min(X, i + person)new_j = min(Y, j + cargo)dp[new_i][new_j] = min(dp[new_i][new_j], dp[i][j] + cost)return dp[X][Y]# 主函数
if __name__ == "__main__":result = min_cost_for_car_purchase()print(result)

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 定义汽车配置方案结构体
struct CarOption {int cost;   // 价格int person; // 载人能力int cargo;  // 载货能力
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int X, Y, n;cin >> X >> Y >> n;// 存储所有汽车配置方案vector<CarOption> opts;// 处理每种汽车型号for (int i = 0; i < n; i++) {int m, x, y, k;cin >> m >> x >> y >> k;// 添加默认配置opts.push_back({m, x, y});// 添加选配方案for (int j = 0; j < k; j++) {int m_add, x_add, y_add;cin >> m_add >> x_add >> y_add;opts.push_back({m + m_add, x + x_add, y + y_add});}}// 初始化dp数组const int INF = 1e9;vector<vector<int>> dp(X + 1, vector<int>(Y + 1, INF));dp[0][0] = 0;// 动态规划求解for (int i = 0; i <= X; i++) {for (int j = 0; j <= Y; j++) {if (dp[i][j] == INF) continue;// 尝试每种配置方案for (const auto& opt : opts) {int new_i = min(X, i + opt.person);int new_j = min(Y, j + opt.cargo);dp[new_i][new_j] = min(dp[new_i][new_j], dp[i][j] + opt.cost);}}}cout << dp[X][Y] << endl;return 0;
}

• Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 定义汽车配置方案类static class CarOption {int cost;   // 价格int person; // 载人能力int cargo;  // 载货能力CarOption(int cost, int person, int cargo) {this.cost = cost;this.person = person;this.cargo = cargo;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取输入int X = sc.nextInt();int Y = sc.nextInt();int n = sc.nextInt();// 存储所有汽车配置方案List<CarOption> options = new ArrayList<>();// 处理每种汽车型号for (int i = 0; i < n; i++) {int m = sc.nextInt();int x = sc.nextInt();int y = sc.nextInt();int k = sc.nextInt();// 添加默认配置options.add(new CarOption(m, x, y));// 添加选配方案for (int j = 0; j < k; j++) {int mAdd = sc.nextInt();int xAdd = sc.nextInt();int yAdd = sc.nextInt();options.add(new CarOption(m + mAdd, x + xAdd, y + yAdd));}}// 初始化dp数组final int INF = 1_000_000_000;int[][] dp = new int[X + 1][Y + 1];for (int i = 0; i <= X; i++) {for (int j = 0; j <= Y; j++) {dp[i][j] = INF;}}dp[0][0] = 0;// 动态规划求解for (int i = 0; i <= X; i++) {for (int j = 0; j <= Y; j++) {if (dp[i][j] == INF) continue;// 尝试每种配置方案for (CarOption opt : options) {int newI = Math.min(X, i + opt.person);int newJ = Math.min(Y, j + opt.cargo);dp[newI][newJ] = Math.min(dp[newI][newJ], dp[i][j] + opt.cost);}}}System.out.println(dp[X][Y]);sc.close();}
}