题目理解

我们有一个 $L \times L$ 的网格，四个角有医院。有 $N$ 个患者分布在网格中，每辆救护车从医院出发接患者再返回，每次移动需要 1 单位时间。我们需要判断在时间 $T$ 内是否能救完所有患者。

关键观察

1. 距离计算

对于患者 $i$，到四个医院的距离分别为：

• 医院1 $(1,1)$: $d_1(i) = x_i + y_i - 2$
• 医院2 $(1,L)$: $d_2(i) = x_i + (L - y_i + 1) - 2 = x_i + L - y_i - 1$
• 医院3 $(L,1)$: $d_3(i) = (L - x_i + 1) + y_i - 2 = L - x_i + y_i - 1$
• 医院4 $(L,L)$: $d_4(i) = 2L - x_i - y_i$

2. 时间分析

救护车接一个患者需要往返，所以总时间为 $2 \times \text{距离}$。代码中 t /= 2 是因为我们关心单程时间。

3. 医院分组策略

将四个医院分成两组：

• 组1: 医院1和医院4（对角线方向）
• 组2: 医院2和医院3（另一对角线方向）

算法思路

核心思想：动态规划 + 分治

算法通过枚举分割点，将患者分成两组，分别由两组医院负责。

数据结构设计

1. 排序数组：

   • p[]: 按 $d_1$ 距离排序的患者
   • q[]: 按 $d_3$ 距离排序的患者

2. DP数组：

   • pre[k][st][j]: 前k个患者，状态st，时间j时的最小另一时间
   • suf[k][st][j]: 后k个患者，状态st，时间j时的最小另一时间

算法流程

步骤1：预处理排序

sort(p + 1, p + n + 1, [&](int i, int j) {
    return d1(i) < d1(j);
});
sort(q + 1, q + n + 1, [&](int i, int j) {
    return d3(i) < d3(j);
});

步骤2：枚举分割点

对于每个分割点 $i$，将患者分成两组：

• 组A: 在p中排名 ≤ i 的患者
• 组B: 在p中排名 > i 的患者

步骤3：动态规划计算

前缀DP：

for k = 1 to n:
    st = (患者k属于组B)
    x = 到对应医院的距离
    y = 到另一医院的距离
    for j = t down to 0:
        pre[k][st][j] = min(pre[k][st][j], pre[k-1][st][j-x] + y)

后缀DP：

for k = n down to 1:
    st = (患者k属于组B)  
    x = 到对应医院的距离
    y = 到另一医院的距离
    for j = t down to 0:
        suf[k][st][j] = min(suf[k][st][j], suf[k+1][st][j-x] + y)

步骤4：检查可行性

对于每个分割点 $j$ 和时间分配：

if pre[j][0][p11] + pre[j][1][t-p12] + 
   suf[j+1][0][p21] + suf[j+1][1][t-p23] ≤ t

则存在可行解。

算法正确性

1. 医院分配合理性

通过枚举分割点，确保每个患者被分配到最优的医院组合。

2. 时间计算正确性

DP状态 pre[k][st][j] 表示：

• 处理前k个患者
• 状态st表示患者属于哪组
• 时间j用于主要医院
• 值为需要另一医院的时间

3. 可行性检查

通过检查所有可能的时间分配方案，确保找到最优解。

时间复杂度

• 排序: $O(N \log N)$
• DP预处理: $O(N \times T)$
• 枚举检查: $O(N \times T)$

总复杂度: $O(N \times T)$，在数据范围内可行。

算法优势

1. 巧妙分组: 将四个医院分成两组处理，简化问题
2. 双重DP: 前缀和后缀DP覆盖所有分配方案
3. 高效枚举: 通过分割点枚举所有可能的患者分组

算法标签

• 动态规划
• 排序
• 分治思想
• 枚举

总结

该算法通过巧妙的医院分组和动态规划技术，解决了多救护车调度问题。核心思想是将复杂的多医院调度转化为两组医院的协调问题，通过枚举分割点和DP计算找到最优的时间分配方案。算法设计精妙，效率较高，是该类问题的经典解法。