1 条题解
-
0
题解
题意分析
题目描述了一个渡轮装载车辆的问题:
- 渡轮有左右两条车道,长度限制为米(转换为厘米)。
- 车辆按顺序到达,每辆车有唯一的长度(厘米)。
- 需要按顺序将车辆分配到左或右车道,且两车道总长度均不超过厘米。
- 目标是最大化装载车辆数,并输出分配方案。
解题思路
- 动态规划:使用动态规划记录状态,表示处理前辆车且左车道总长度为时是否可行。
- 状态转移:
- 将第辆车分配到左车道:检查。
- 将第辆车分配到右车道:检查。
- 回溯方案:从最终状态回溯,根据记录的选择方向输出分配方案。
实现步骤
- 输入处理:读取渡轮长度和车辆长度列表,以结束输入。
- 初始化:
- 将渡轮长度转换为厘米()。
- 计算车辆长度的前缀和。
- 动态规划填充:
- 初始化(表示0辆车时左车道长度为0可行)。
- 遍历每辆车和可能的左车道长度,更新状态。
- 确定最大装载数:记录最多能装载的车辆数及其对应的左车道长度。
- 回溯输出方案:根据记录的选择方向反向输出分配方案。
代码注释
#include <map> #include <set> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; int f[510][15010], g[510][15010]; // f[i][s]表示前i辆车左车道长度为s是否可行;g记录选择方向 int a[510], sum[510]; // a存储车辆长度,sum为前缀和 int main() { int m; scanf("%d", &m); // 读取渡轮长度(米) m *= 100; // 转换为厘米 int n = 0, x; // n为车辆数,x为临时变量 while (1) { scanf("%d", &x); // 读取车辆长度 if (x == 0) break; // 输入结束 a[++n] = x; // 存储车辆长度 } for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + a[i]; // 计算前缀和 } f[0][0] = 1; // 初始状态:0辆车时左车道长度为0可行 int mx = 0, sx = 0; // mx为最大车辆数,sx为对应的左车道长度 for (int i = 0; i < n; i++) { // 遍历每辆车 for (int s = 0; s <= 15000; s++) { // 遍历可能的左车道长度 if (f[i][s]) { // 如果前i辆车左车道长度为s可行 int L = s, R = sum[i] - L; // 计算右车道长度 if (L + a[i + 1] <= m) { // 尝试分配到左车道 f[i + 1][L + a[i + 1]] = 1; g[i + 1][L + a[i + 1]] = 1; // 记录方向(1表示左) mx = i + 1, sx = L + a[i + 1]; // 更新最大值 } if (R + a[i + 1] <= m) { // 尝试分配到右车道 f[i + 1][L] = 1; g[i + 1][L] = 2; // 记录方向(2表示右) mx = i + 1, sx = L; // 更新最大值 } } } } printf("%d\n", mx); // 输出最大车辆数 vector<char*> ans; // 存储分配方案 while (mx) { // 回溯方案 if (g[mx][sx] == 1) { // 如果分配到左车道 ans.push_back("port"); sx -= a[mx]; // 更新左车道长度 mx--; } else { // 如果分配到右车道 ans.push_back("starboard"); mx--; } } for (int i = ans.size() - 1; i >= 0; i--) { // 反向输出方案 printf("%s\n", ans[i]); } return 0; }
复杂度分析
- 时间复杂度:动态规划的状态数为,其中为车辆数,为渡轮长度(米)。总复杂度为。
- 空间复杂度:使用两个二维数组和,空间复杂度为。
- 1
信息
- ID
- 1610
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者