题解：P14418 [JOISC 2014] 巴士走读 / Bus

· · 题解

排序 + 二分

题意

给定 n 个站点，m 趟巴士：a,b,x,y 表示 x 时刻从 a 出发，y 时刻到达 b 的巴士。

JOI 君可以换乘公交车，只要前一辆到达当前站的时间 \le 下一辆从该站的发车时间即可，换乘时间忽略。

给定 q 次询问，每次给定一个数 L_j，求 JOI 君最晚可以在什么时刻从公交站 1 出发，才能按时到达；若无法到达，输出 -1。

做法

我们要求在时间 t 前到达每个点的最晚出发时间 st，这里的 st 指从起点的最晚出发时间。

我们按到达时间 y 从小到大排序，这样枚举到的第 i 个巴士一定是当前到达 b 的最迟的巴士。

所以对于每一个点 j，我们维护 pos[b] 表示到达 b 的时间序列，因为排序所以有序；ans[b] 表示在某一时间之前能到达站点 b 的最晚出发时间。

对于每一条巴士路径，我们在 a 站点二分第一个小于等于 x 时刻的最晚出发时间，如果它大于目前 b 站点的最晚出发时间那就加上，否则这劣于答案对答案无贡献。（这是贪心的思想，最晚出发时间肯定是要尽可能的晚，所以我们取最大值，并且这一步保证了答案维度的升序）。

特别的，站点为起点的最晚出发时间就是每条从起点出发的巴士的出发时间。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10; 
template<typename TY>
inline void read(TY &s){
    ll x = 0,f = 1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    s = x * f;
}
int n,m,q;
struct node{
    int a,b,x,y;
}z[N];
bool cmp(node a,node b){
    return a.y < b.y; 
}
vector<int> ans[N],pos[N];
int main(){
    read(n); read(m);
    for(int i=1;i<=m;i++){
        read(z[i].a); read(z[i].b); read(z[i].x); read(z[i].y);
    } 
    sort(z+1,z+m+1,cmp);
    for(int i=1;i<=n;i++) ans[i].push_back(-1),pos[i].push_back(0);
    for(int i=1;i<=m;i++){
        int a = z[i].a,b = z[i].b,x = z[i].x,y = z[i].y;
        int maxn;
        if(a == 1) maxn = x;
        else maxn = ans[a][upper_bound(pos[a].begin(),pos[a].end(),x) - pos[a].begin() - 1];
        if(maxn > ans[b][pos[b].size()-1]) ans[b].push_back(maxn),pos[b].push_back(y);
    }
    read(q);
    int l = 0;
    while(q--){
        read(l);
        cout << ans[n][upper_bound(pos[n].begin(),pos[n].end(),l) - pos[n].begin() - 1] << "\n"; 
    }
    return 0;
}