「ROI 2024 Day1」飞行箱 题解

题目大意

有 $n$ 个座位排成一排，坐标从 $1$ 到 $n$。餐车从坐标 $0$ 出发，需要到达坐标 $n+1$。有 $k$ 种饮料，第 $i$ 个座位的乘客需要饮料类型 $a_i$。每瓶饮料可以装 $p$ 份，餐车最多装 $m$ 瓶。储藏室位置由 $c$ 决定：

• $c=1$：只在 $n+1$ 处
• $c=2$：只在 $0$ 处
• $c=3$：两端都有

求服务所有乘客的最短移动距离。

解题思路

关键观察

1. 区间覆盖：每种饮料的需求可以看作若干区间，每个区间表示一瓶饮料服务的连续座位段
2. 动态规划：用 $f[i]$ 表示服务完前 $i$ 个座位的最小距离
3. 贪心优化：使用优先队列维护最优转移

代码详解

数据结构定义

const int N = 1e6 + 5;
int n, m, k, p, C, req[N], val[N];
vector<int> e[N], ed[N]; // 区间端点

• req[i]：第 $i$ 个座位需要的饮料类型
• e[i]：以 $i$ 为左端点的区间右端点
• ed[i]：以 $i$ 为右端点的区间左端点
• val[i]：从位置 $i$ 到最近储藏室的往返代价

预处理阶段

void Prepare() {
    static int tmp[N], curl[N];
    
    for (int i = 1; i <= n; i++) {
        if (!tmp[req[i]]) {  // 新开一瓶饮料
            curl[req[i]] = i;  // 记录区间起点
            tmp[req[i]] = p;   // 重置容量
        }
        
        tmp[req[i]]--;  // 消耗一份
        
        if (!tmp[req[i]]) {  // 这瓶饮料用完
            e[curl[req[i]]].push_back(i);    // 记录区间 [l, r]
            ed[i].push_back(curl[req[i]]);
            curl[req[i]] = 0;
        }
    }
    
    // 处理未用完的饮料
    for (int i = 1; i <= k; i++)
        if (curl[i])
            e[curl[i]].push_back(n + 1), ed[n + 1].push_back(curl[i]);
    
    // 计算到储藏室的代价
    for (int i = 0; i <= n + 1; i++)
        val[i] = min((C & 1) ? (2 * (n + 1 - i) - 1) : 2 * N, 
                    (C & 2) ? (2 * i + 1) : 2 * N);
}

预处理逻辑：

1. 区间划分：将每种饮料的需求划分为若干长度为 $p$ 的区间
2. 储藏室代价：
   • 如果 $c=1$（终点有储藏室），代价为 $2(n+1-i)-1$
   • 如果 $c=2$（起点有储藏室），代价为 $2i+1$
   • 如果 $c=3$（两端都有），取最小值

动态规划求解

void DP() {
    memset(f, 0x3f, sizeof f), f[0] = 0;
    int l = 0;
    priority_queue<int, vector<int>, greater<int>> pq, del;
    pq.push(f[0] - 0 + 1), pv[0] = f[0] - 0 + 1;
    int middle = 0, rest = m;
    
    for (int i = 1; i <= n + 1; i++) {
        middle += e[i].size();  // 新增以i开始的区间
        
        // 滑动窗口：确保当前使用的瓶子数不超过m
        while (middle > rest)
            del.push(pv[l]), l++, 
            rest += ed[l].size(), rest -= e[l].size(), middle -= e[l].size();
        
        // 清理无效元素
        while (!del.empty() and del.top() == pq.top())
            del.pop(), pq.pop();
        
        // 状态转移
        if (!pq.empty())
            f[i] = pq.top() + i - 1;
        
        pq.push(f[i] + val[i] - i);
        pv[i] = f[i] + val[i] - i;
    }
    
    cout << f[n + 1];
}

DP核心思想：

• f[i]：服务完前 $i$ 个座位的最小距离
• 状态转移：$f[i] = \min_{j < i} \{f[j] + \text{cost}(j, i)\}$
• 使用优先队列维护 $f[j] + \text{val}[j] - j$ 的最小值
• 滑动窗口确保任何时候使用的瓶子数不超过 $m$

复杂度分析

• 时间复杂度：$O(n \log n)$，每个位置入队出队一次
• 空间复杂度：$O(n)$，存储区间信息和优先队列

算法正确性

该算法通过将问题转化为区间覆盖和动态规划，利用优先队列优化转移，确保了在满足容量限制的前提下找到最短路径。预处理阶段正确划分了饮料服务区间，DP阶段通过滑动窗口维护了容量约束。

总结

本题的关键在于将饮料服务建模为区间覆盖问题，然后使用带容量约束的动态规划求解。算法通过巧妙的预处理和数据结构优化，在 $O(n \log n)$ 时间内解决了问题。