#5481. 「UOI 2016 Stage 4 Day1」机器人 题解

问题分析

机器人需要配送 $N$ 件礼物到不同的房屋，每次最多携带 $K$ 件礼物。关键约束：

• 行驶距离 = 时间（1公里/分钟）
• 装卸礼物 = 1分钟/件
• 必须返回邮局

核心观察

1. 时间组成

总时间 = 行驶时间 + 装卸时间

由于每次装卸都需要时间，且必须返回邮局：

• 装卸时间固定 = $2 \times N$ 分钟（每件礼物装卸各1次）
• 关键是最小化行驶时间

2. 配送策略

最优策略是将最远的房屋优先配送，并且每次尽量装满 $K$ 件礼物。

算法思路

贪心策略

1. 排序房屋：按距离从大到小排序
2. 分组配送：每次取最远的 $K$ 个房屋进行配送
3. 计算行驶时间：每次往返最远房屋的距离 $\times 2$

数学推导

设排序后的房屋距离为 $d_1 \geq d_2 \geq \dots \geq d_N$

分组情况：

• 第1组：$d_1, d_2, \dots, d_K$ → 行驶距离 = $2 \times d_1$
• 第2组：$d_{K+1}, d_{K+2}, \dots, d_{2K}$ → 行驶距离 = $2 \times d_{K+1}$
• ...
• 第$m$组：剩余房屋 → 行驶距离 = $2 \times d_{(m-1)K+1}$

总行驶时间 = $\sum 2 \times d_{(i-1)K+1}$

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<int> houses(N);
    for (int i = 0; i < N; i++) {
        cin >> houses[i];
    }
    
    // 按房屋距离从大到小排序
    sort(houses.begin(), houses.end(), greater<int>());
    
    // 计算总时间
    long long total_time = 0;
    
    // 行驶时间：每组配送最远房屋距离的2倍
    for (int i = 0; i < N; i += K) {
        total_time += 2LL * houses[i];
    }
    
    // 装卸时间：每件礼物装卸各1分钟
    total_time += 2LL * N;
    
    cout << total_time << endl;
    
    return 0;
}

复杂度分析

• 排序：$O(N \log N)$
• 分组计算：$O(N)$
• 总复杂度：$O(N \log N)$，适合 $N \leq 10^5$

样例验证

样例输入

7 3
3 9 3 2 1 1 3

计算过程

1. 排序房屋：9, 3, 3, 3, 2, 1, 1
2. 分组：
   • 第1组：9, 3, 3 → 行驶 2×9 = 18分钟
   • 第2组：3, 2, 1 → 行驶 2×3 = 6分钟
   • 第3组：1 → 行驶 2×1 = 2分钟
3. 行驶时间：18 + 6 + 2 = 26分钟
4. 装卸时间：2×7 = 14分钟
5. 总时间：26 + 14 = 40分钟 ✓

正确性证明

为什么贪心最优？

1. 最远优先：如果不先送最远的，后续需要额外往返
2. 满载配送：每次尽量带满 $K$ 件，减少往返次数
3. 往返必须：由于必须返回邮局，每次配送最远距离决定该组行驶时间

时间计算

• 行驶时间：$\sum_{i=0}^{\lceil N/K \rceil-1} 2 \times d_{iK}$
• 装卸时间：$2N$（固定）

边界情况处理

// 防止整数溢出
total_time += 2LL * houses[i];

// 处理空输入
if (N == 0) {
    cout << 0 << endl;
    return 0;
}

总结

本题的关键在于发现：

1. 装卸时间是固定的 $2N$
2. 行驶时间由分组后每组最远房屋决定
3. 贪心策略：最远房屋优先配送，每次尽量满载

算法简洁高效，时间复杂度 $O(N \log N)$，能够处理最大数据规模。