题解：P11178 [ROIR 2018 Day1] 电梯

· · 题解

题意

一座有 m 层的大厦内有 n 个员工即将下班，他们将要前往一楼。对于编号 i 的员工，他位于 a_i 层且 t_i 秒后他会到达电梯口给电梯发送信号并等待电梯。

电梯每秒可以上升或下降一层。若它收到信号它会优先响应最早的信号，同时接受的信号中优先响应编号最小员工的信号。

每当电梯接受信号，它从一层出发来到发出信号的那一层，然后回到一层，它在下降的过程中如果有人已经在等待也会一同承载电梯来到一层。

问按照已有信息，每个员工抵达一层的时间。

思路

先根据题意，按照电梯接受信号的优先级对员工信息排序，然后模拟电梯移动过程。

令当前时间为 nt，使用队列 q 存储 nt 前待处理的信号。

模拟时，每次从队头取出一个信号 i 收到该信号时间为 t_i，则楼层为 a_i，所以电梯出发时间为 \max(nt,t_i)，电梯抵达 a_i 用时为 u=a_i-1。

此次接到的员工有两种，一种是发出信号的员工，还有电梯接完发出信号员工后往下走时遇到的在电梯口等待的员工。这些员工抵达一层的时间是一样为 \max(nt,t_i)+u\times2。

问题的重点在于确定会被接走的员工编号是哪些。对于第一种员工，编号已经得到了，不作讨论。对于第二种员工，又分为两种了，一种是在电梯出发前就已经在 a_i 层及其一下等待了，还有一种是电梯出发后才赶到电梯口的。

对于电梯出发前就已经在等待的员工，他们肯定在 q 内。但是我们对于员工信息的排序方式使得我们无法高效的查找到那些位于 a_i 楼层下的员工，所以我们开一个优先队列，内按照 a 从小到大排序，单独维护这一类员工。

对于电梯出发后才赶到电梯口的，他们赶到电梯口的时间一定是在区间 [\max(nt,t_i),\max(nt,t_i)+u\times 2] 内的，我们接受时间在这个区间内的信号，然后判断电梯下降来到这些楼层后这些员工能否赶上电梯。

同一个信号会被优先队列和队列同时接收，但是出答案时只会从一个地方弹出，所以在处理这些信号时要特判是否已经被弹出，免得重复计算导致答案错误。

update:2025/8/25 更新了放错的代码

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,cnt;
long long nt,ans[N];
struct pl{
    int id,t,a;
    bool operator<(pl b)const{
        return a>b.a;
    }
}p[N];
inline bool cmp(pl a,pl b){
    return a.t!=b.t?a.t<b.t:a.id<b.id;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,t,a;i<=n;i++){
        scanf("%d%d",&t,&a);
        p[i]={i,t,a};
    }
    sort(p+1,p+n+1,cmp);
    queue<pl>q;
    priority_queue<pl>qq;
    while(cnt<n||!q.empty()){
        if(q.empty()){
            q.push(p[++cnt]);
            qq.push(p[cnt]);
        }
        int h=q.front().a;
        int u=h-1;
        nt=max(nt,(long long)q.front().t);
        ans[q.front().id]=nt+u*2;
        q.pop();
        while(!qq.empty()){
            if(ans[qq.top().id])qq.pop();
            else if(qq.top().a<=h){
                ans[qq.top().id]=nt+u*2;
                qq.pop();
            }
            else break;
        }
        while(cnt<n&&p[cnt+1].t<=nt+u*2){
            ++cnt;
            if(p[cnt].a<=h&&p[cnt].t<=nt+u+h-p[cnt].a)
                ans[p[cnt].id]=nt+u*2;
            else{
                q.push(p[cnt]);
                qq.push(p[cnt]);
            }
        }
        while(!q.empty()&&ans[q.front().id])q.pop();
        nt+=u*2;
    }
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}