「ROI 2024 Day1」无人机物流 题解

题目分析

本题需要在一系列障碍物和配送窗口的事件序列中，找到最优的配送策略以最大化利润。关键点在于理解障碍物对机器人纵队的影响，以及如何在克隆成本与配送收入之间取得平衡。

核心思路

关键观察

1. 障碍物的累积效应：障碍物会截断低于其高度的机器人，只有高于障碍物的机器人能继续前进
2. 高度转换：每个配送窗口的实际高度需要加上之前所有障碍物的高度总和
3. 贪心策略：优先配送高度较低的窗口，因为需要的克隆次数更少

算法实现

数据结构

• sum：记录累计障碍物高度
• clo：存储所有配送窗口调整后的高度

代码详解

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in", "r", stdin), freopen(Plus_Cat ".out", "w", stdout);
#endif
    I(n, m, C, P);  // 输入障碍物数n、订单数m、克隆成本C、配送收入P
    FOR(i, 1, n + m) {
        int opt;
        ll h;
        I(opt, h);  // 输入事件类型opt和高度h
        
        if (opt == 1)
            sum += h;  // 累加障碍物高度
        else
            h += sum - 1, clo.push_back(h);  // 调整窗口高度并存储
    }

关键步骤解释：

• 当遇到障碍物（opt == 1）时，累加其高度到sum中
• 当遇到配送窗口（opt == 2）时，实际需要的高度为 $h + sum - 1$
  • $sum$：之前所有障碍物的累计高度
  • $-1$：因为初始有1个机器人，高度从1开始计数

    sort(clo.begin(), clo.end());  // 按调整后高度升序排序
    FOR(i, 1, clo.size())
        tomax(ans, (ll)i * P - (ll)clo[i - 1] * C);  // 计算最大利润
    O(ans, '\n');
    return 0;
}

利润计算： 对于前 $i$ 个最低的窗口，利润计算公式为：

其中：

• $i \times P$：配送 $i$ 个订单的总收入
• $\text{clo}[i-1] \times C$：达到第 $i$ 个窗口高度所需的总克隆成本

算法正确性证明

为什么排序后贪心有效？

1. 成本单调性：高度越低的窗口，所需的克隆次数越少
2. 独立性：配送较低窗口的机器人可以继续用于配送较高窗口
3. 最优子结构：前 $i$ 个最优解必然包含前 $i-1$ 个最优解

时间复杂度

• 读取输入：$O(n+m)$
• 排序：$O(m \log m)$
• 利润计算：$O(m)$
• 总复杂度：$O((n+m) + m \log m)$，在数据范围内可行

示例分析

样例1

输入：2 3 2 6
事件序列：
障碍物 h=2 → sum=2
窗口 h=3 → 实际高度=2+3-1=4
障碍物 h=1 → sum=3
窗口 h=6 → 实际高度=3+6-1=8
窗口 h=2 → 实际高度=3+2-1=4

排序后窗口高度：[4,4,8]
利润计算：
i=1: 1×6 - 4×2 = -2
i=2: 2×6 - 4×2 = 4
i=3: 3×6 - 8×2 = 2
最大利润：4

总结

本题通过巧妙的高度转换和贪心排序，将复杂的动态规划问题简化为 $O(m \log m)$ 的解法。核心在于理解障碍物的累积效应，以及如何将配送决策转化为对排序后序列的线性扫描。