P5688 [CSP-S2019 江西] 散步 题解

发布于 2021-08-13  92 次阅读


题目链接

看到题解区清一色的解法都好麻烦……贡献一发纯代码 2k 以内(还有两段重复)的堆+链表解法。

文章目录

解析

考虑暴力,就是每次找到一个离出口最近的人,让他走到出口,如果发现他想走的那个出口不能走了,将他的出口重新指定为往后走的最近的那个出口并重新计算记录。重复上述过程直至出口出不了人了或所有人都走完了。

考虑用数据结构维护这个暴力,我们在结构体里用 $id,opt,to,dis$​​​​ 分别存储一个人的编号、方向、目的地和到目的地的距离,以 $dis$​ 为关键字将其扔进堆里。然后我们每次从队首取出元素,判断这个人能否离开,能离开就离开,不能就暴力往后走直至走到第一个可以走的出口,更新其的 $to,dis$​ 两个元素再把它重新扔进堆里。同时,我们发现如果一个人的 $dis\ge L$,就说明其走了一圈还没有找到可以走的出口,这样他就不可能找到出口了,直接退出即可。不精心构造的数据下跑的挺快,所以直接得到了 90pts 的好成绩。

接着考虑复杂度瓶颈在每次暴力往后走这个事情上,到后期大部分出口都不能走时,该操作会白白耗费大量时间。我们想到用链表优化。由于一个出口不可用之后对我们的答案不会产生任何贡献,我们考虑将所有出口用链表连接,如果一个出口不可用了,就将他从链表中删除。我们发现我们每次取堆顶元素至少可以让一个人走出去或删除一个出口,因此复杂度为 $O((n+m)\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,L,li[N];
int a[N],ans[N],l[N],r[N];
long long ANS;
struct node{
    int id,opt,to,dis;//编号 方向 目的地 距离.
    bool operator <(const node &x)const{
        if(dis!=x.dis) return x.dis<dis;
        return x.id<id;
    }
}b[N];
priority_queue<node> q;
inline void del(int x){
    r[l[x]]=r[x];
    l[r[x]]=l[x];
}
bool fl;
int main(){
    scanf("%d%d%d",&n,&m,&L);
    for(int i=2;i<=m;i++) scanf("%d",&a[i]);
    a[m+1]=L;
    for(int i=1;i<=m;i++) scanf("%d",&li[i]);
    for(int i=1;i<=m;i++) l[i]=i-1,r[i]=i+1;
    l[1]=m;r[m]=1;
    for(int i=1,opt,pos;i<=n;i++){
        scanf("%d%d",&opt,&pos);
        int now=lower_bound(a+1,a+1+m,pos)-a;
        if(a[now]==pos) q.push((node){i,opt,now,0});
        else if(opt==0){
            int dis=a[now]-pos;
            if(now>m) now=1;
            q.push((node){i,opt,now,dis});
        }
        else{
            now--;
            q.push((node){i,opt,now,pos-a[now]});
        }
    }//初始化,找每个人的第一个目的地
    while(!q.empty()){
        if(fl) break;
        node c=q.top();q.pop();
        if(li[c.to]){li[c.to]--;ans[c.id]=c.to;continue;}
        int dis=c.dis,now=c.to;
        if(c.opt==0){//按方向分类讨论
            while(li[now]==0){
                del(now);//不可用的出口删除掉
                int pre=now;
                now=r[now];
                if(pre==now){fl=1;break;}//出口都删完了,直接退出即可。
                if(a[now]<a[pre]) dis+=L-a[pre]+a[now];
                else dis+=a[now]-a[pre];//重新计算距离
                if(dis>=L&&li[now]==0){fl=1;break;}//走了一圈找不到出口,也可以直接退出
            }
            if(!fl){
                q.push((node){c.id,c.opt,now,dis});
            }
        }
        else{//其实这两段差不多
            while(li[now]==0){
                del(now);
                int pre=now;
                now=l[now];
                if(pre==now){fl=1;break;}
                if(a[now]>a[pre]) dis+=L-a[now]+a[pre];
                else dis+=a[pre]-a[now];
                if(dis>=L&&li[now]==0){fl=1;break;}
            }
            if(!fl){
                q.push((node){c.id,c.opt,now,dis});
            }
        }
    }
    for(int i=1;i<=n;i++) ANS^=((long long)i*ans[i]);
    printf("%lld\n",ANS);
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣