1 条题解

  • 0
    @ 2025-6-5 12:45:30

    题解

    题意分析

    题目描述了一个渡轮装载车辆的问题:

    • 渡轮有左右两条车道,长度限制为LL米(转换为100L100L厘米)。
    • 车辆按顺序到达,每辆车有唯一的长度(厘米)。
    • 需要按顺序将车辆分配到左或右车道,且两车道总长度均不超过100L100L厘米。
    • 目标是最大化装载车辆数NN,并输出分配方案。

    解题思路

    1. 动态规划:使用动态规划记录状态f[i][s]f[i][s],表示处理前ii辆车且左车道总长度为ss时是否可行。
    2. 状态转移
      • 将第i+1i+1辆车分配到左车道:检查s+a[i+1]100Ls + a[i+1] \leq 100L
      • 将第i+1i+1辆车分配到右车道:检查sum[i]s+a[i+1]100Lsum[i] - s + a[i+1] \leq 100L
    3. 回溯方案:从最终状态回溯,根据记录的选择方向输出分配方案。

    实现步骤

    1. 输入处理:读取渡轮长度LL和车辆长度列表,以00结束输入。
    2. 初始化
      • 将渡轮长度转换为厘米(100L100L)。
      • 计算车辆长度的前缀和sum[i]sum[i]
    3. 动态规划填充
      • 初始化f[0][0]=1f[0][0] = 1(表示0辆车时左车道长度为0可行)。
      • 遍历每辆车和可能的左车道长度,更新状态。
    4. 确定最大装载数:记录最多能装载的车辆数mxmx及其对应的左车道长度sxsx
    5. 回溯输出方案:根据记录的选择方向反向输出分配方案。

    代码注释

    #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;
    }
    

    复杂度分析

    • 时间复杂度:动态规划的状态数为O(n×100L)O(n \times 100L),其中nn为车辆数,LL为渡轮长度(米)。总复杂度为O(n×15000)O(n \times 15000)
    • 空间复杂度:使用两个二维数组ffgg,空间复杂度为O(n×15000)O(n \times 15000)
    • 1

    信息

    ID
    1610
    时间
    1000ms
    内存
    64MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者