专栏文章

题解：P11986 [JOIST 2025] 救护车 / Ambulance

ccuijiexiong
P11986题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miniryes
此快照首次捕获于
2025/12/02 03:05
3 个月前
此快照最后确认于
2025/12/02 03:05
3 个月前
查看原文
我做这题时，没看懂别人的题解（我还是太菜了），搞了好久（2 天）才想出来，还是和同学讨论的情况下。还是自己写一篇题解好。

题目大意

有一个 L×LL \times L 的方格区域，四个角各有一家医院，每家医院配备一辆救护车。每辆救护车一次只能运送一个病人，且每单位时间只能移动到相邻的格子。现有 NN 个病人，第 ii 个病人位于 (Xi,Yi)(X_i, Y_i)。请判断是否所有病人都能在时间 TT 内被送到任意一家医院。

解题思路

初步分析

由于救护车需要往返，我们先将 TT 除以 22，这样在后续计算中就不需要再乘以 22 了。下文中提到的 TT 均为除以 22 之后的值。
我们将四家医院编号如下：
  • ① 位于 (1,1)(1, 1)。
  • ② 位于 (1,L)(1, L)。
  • ③ 位于 (L,1)(L, 1)。
  • ④ 位于 (L,L)(L, L)。
四个医院的情况稍显复杂，我们先从两个医院的情况入手，以对角线上的 ① 和 ④ 为例。
一个病人可以选择去 ① 或 ④，所需时间分别为 x+y−2x + y - 2 和 2L−(x+y)2L - (x + y)。我们将所有病人按照到 ① 的时间排序，通过贪心策略可以发现，最优方案中去 ① 的病人是排序后的一个前缀，而去 ④ 的病人是一个后缀。
可以证明这是不劣的：
假设有两个病人 ii 和 jj，坐标分别为 (xi,yi)(x_i, y_i) 和 (xj,yj)(x_j, y_j)，且 ii 去 ①，jj 去 ④。若 xi+yi−2>xj+yj−2x_i + y_i - 2 > x_j + y_j - 2，
则可推出 2L−xi−yi<2L−xj−yj2L - x_i - y_i < 2L - x_j - y_j。
基于这两个不等式，将 jj 分配去 ①，ii 分配去 ④ 显然是更优的选择。
因此，我们只需枚举中间的分界点即可确定最优分配。
回到原问题，另一条对角线上的 ② 和 ③ 的分配也是类似的：按到 ② 的距离排序，去 ② 的病人是排序后的一个前缀，去 ③ 的是一个后缀。

考虑 DP

然而，上述分析仅考虑了同一对角线上的医院分配，未考虑病人是去 ①④ 还是去 ②③。
我们先将所有病人按到 ① 的距离排序，并枚举去 ① 和去 ④ 的分界点。这样我们将病人分为两部分：左边的病人可以去 ①、②、③，右边的病人可以去 ②、③、④。接着，我们将左边和右边的病人分别按到 ② 的距离排序。由于左右两部分处理方式类似，下面我们以左边为例进行说明。
排序后，我们枚举左边去 ② 和去 ③ 的分界点，将左边进一步分为两部分：左左半（可去 ①、②）和左右半（可去 ①、③）。下图展示了左左半、左右半、右左半、右右半的划分：
通过上述划分，我们将整个序列分成了四个部分。这四个部分的处理方式类似，这里我们以左左半为例进行讨论。
考虑使用动态规划（DP）。定义状态 dpi,jdp_{i,j} 表示考虑左左半的前 ii 个病人，其中去 ① 的总用时为 jj 时，去 ② 的最小总用时。转移方程如下：
dpi,j=min⁡(dpi−1,j+to(i,2), dpi−1,j−to(i,1))dp_{i,j} = \min(dp_{i-1,j} + \text{to}(i,2),\ dp_{i-1,j - \text{to}(i,1)})
其中 to(i,j)\text{to}(i,j) 表示第 ii 个病人到医院 jj 的用时。边界情况需特判避免越界。
类似地，我们为其他三个部分也定义 DP 状态：
  • f0,i,jf_{0,i,j}：左左半前 ii 个病人，去 ① 总用时为 jj 时，去 ② 的最小总用时。
  • g0,i,jg_{0,i,j}：左右半后 ii 个病人，去 ① 总用时为 jj 时，去 ③ 的最小总用时。
  • f1,i,jf_{1,i,j}：右左半前 ii 个病人，去 ② 总用时为 jj 时，去 ④ 的最小总用时。
  • g1,i,jg_{1,i,j}：右右半后 ii 个病人，去 ③ 总用时为 jj 时，去 ④ 的最小总用时。
这些 DP 状态有什么用呢？题目只要求判断是否能在时间 TT 内完成运送，并不需要求出具体的最小时间。结合 DP 状态中 jj 越大、DP 值越小的单调性，我们可以通过以下步骤进行判断：
  1. 枚举左左半去 ① 的总用时 t1t_1。
  2. 计算 t2=f0,k1,t1t_2 = f_{0,k_1,t_1} 和 t3=g0,k2,T−t1t_3 = g_{0,k_2,T - t_1}。
  3. 计算 t4=f1,k3,T−t2+g1,k4,T−t3t_4 = f_{1,k_3,T - t_2} + g_{1,k_4,T - t_3}。
  4. 若 t4≤Tt_4 \le T，则输出 Yes。

优化

我们来分析一下时间复杂度：
  • 枚举四个部分的分界线：O(n3)O(n^3)。
  • 进行 DP 计算：O(nT)O(nT)。
总时间复杂度为 O(n4T)O(n^4T)，显然无法接受。
回顾我们最初的分析：按到 ① 的距离排序后，去 ① 的病人一定是一个前缀；按到 ② 的距离排序后，去 ② 的病人也一定是一个前缀。而我们之前枚举四个部分的分界线时，并未保证去 ② 的病人是前缀，导致效率低下。具体优化方法如下图所示（~有点不想写了~）：
通过这种方式，我们将枚举分界线的时间复杂度降为 O(n2)O(n^2)。
需要注意的是，DP 计算其实和四半的分界线无关，可以在枚举分界线之前预处理完成，就类似前缀后缀优化。
最终时间复杂度就为 O(n2T)O(n^2T)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205,Tx=2e4+100;
int L,n,T,coin;
int f[2][N][Tx],g[2][N][Tx];
struct node{
    int x,y,id;
};
node a[N],b[N],ra[N];

// 计算病人X到医院op的用时
int to(node X,int op){
    int x=X.x,y=X.y;
    if(op==1) return x+y-2;      // 到①医院的时间
    if(op==2) return L-1+x-y;    // 到②医院的时间  
    if(op==3) return L-1-x+y;    // 到③医院的时间
    if(op==4) return 2*L-x-y;    // 到④医院的时间
}

// 按到①医院的距离排序
bool cmp1(node x,node y){
    return to(x,1)<to(y,1);
}

// 按到②医院的距离排序，距离相同时按到①的距离排序
bool cmp2(node x,node y){
    if(to(x,2)==to(y,2)) return to(x,1)<to(y,1);
    return to(x,2)<to(y,2);
}

// DP预处理：tl到tr区间，To表示主要医院，is表示是否交换医院角色
void get_dp(int tl,int tr,int To,bool is){
    sort(a+tl,a+1+tr,cmp2);  // 对区间内病人按到②的距离排序
    
    // 初始化DP数组
    for(int i=0;i<=T;i++)
        f[is][tl-1][i]=g[is][tr+1][i]=0;
    
    // 前向DP：f[is][i][j]表示前i个病人，去主要医院总时间为j时，去次要医院的最小总时间
    for(int i=tl;i<=tr;i++){
        for(int j=0;j<=T;j++){
            int x=to(a[i],To),y=to(a[i],2);  // x去主要医院时间，y去次要医院时间
            if(is) swap(x,y);  // 如果is为真，交换医院角色
            f[is][i][j]=f[is][i-1][j]+y;  // 当前病人去次要医院
            if(j>=x) f[is][i][j]=min(f[is][i][j],f[is][i-1][j-x]);  // 当前病人去主要医院
        }
    }
    
    // 后向DP：g[is][i][j]表示从i到tr的病人，去主要医院总时间为j时，去次要医院的最小总时间
    for(int i=tr;i>=tl;i--){
        for(int j=0;j<=T;j++){
            int x=to(a[i],To),y=to(a[i],3);  // x去主要医院时间，y去次要医院时间
            if(is) swap(x,y);  // 如果is为真，交换医院角色
            g[is][i][j]=g[is][i+1][j]+y;  // 当前病人去次要医院
            if(j>=x) g[is][i][j]=min(g[is][i][j],g[is][i+1][j-x]);  // 当前病人去主要医院
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>L>>n>>T;
    T/=2;  // 因为救护车需要往返，所以时间除以2
    
    // 读入病人坐标并计算最小总时间（用于初步剪枝）
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        coin+=min(min(to(a[i],1),to(a[i],2)),min(to(a[i],3),to(a[i],4)));
    }
    
    // 如果最小总时间已经超过T，直接输出No
    if(coin/4>T){
        cout<<"No";
        return 0;
    }
    
    // 按到①医院的距离排序
    sort(a+1,a+1+n,cmp1);
    
    // 建立按到②医院距离排序的映射
    for(int i=1;i<=n;i++) b[i]=a[i],b[i].id=i;
    sort(b+1,b+1+n,cmp2);
    for(int i=1;i<=n;i++) a[b[i].id].id=i;
    
    // 备份原始数组
    for(int i=1;i<=n;i++)
        ra[i]=a[i];
    
    // 枚举去①和去④的分界点V
    for(int V=0;V<=n;V++){
        // 预处理左边区间[1,V]和右边区间[V+1,n]的DP
        get_dp(1,V,1,0);   // 左边：主要医院①，次要医院②
        get_dp(V+1,n,4,1); // 右边：主要医院④，次要医院②（is=1表示交换角色）
        
        // 枚举去②和去③的分界点U
        for(int U=0,L=0,R=V;U<=n;U++){
            // 维护左左半大小L和右左半大小R
            if(L<V&&a[L+1].id<=U) L++;
            if(R<n&&a[R+1].id<=U) R++;
            
            // 枚举左左半去①的总时间t1
            for(int t1=0;t1<=T;t1++){
                int t2=f[0][L][t1];        // 左左半去②的最小总时间
                int t3=g[0][L+1][T-t1];    // 左右半去③的最小总时间
                
                if(t2>T||t3>T) continue;   // 如果时间超限，跳过
                
                // 计算右边去④的总时间
                int t4=f[1][R][T-t2]+g[1][R+1][T-t3];
                
                if(t4<=T){  // 如果所有时间都在限制内
                    cout<<"Yes";
                    return 0;
                }
            }
        }
        
        // 恢复原始数组，为下一次枚举做准备
        for(int i=1;i<=n;i++)
            a[i]=ra[i];
    }
    
    cout<<"No";
    return 0;
}
代码经 AI 注释，但其他都是我写的。~有点懒，不想写注释了。~
求管理员让过。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...