专栏文章

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

qqdl66666666
P14418题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mincqba6
此快照首次捕获于
2025/12/02 00:16
3 个月前
此快照最后确认于
2025/12/02 00:16
3 个月前
查看原文

排序 + 二分

题意

给定 nn 个站点，mm 趟巴士：a,b,x,ya,b,x,y 表示 xx 时刻从 aa 出发，yy 时刻到达 bb 的巴士。
JOI 君可以换乘公交车，只要前一辆到达当前站的时间 ≤\le 下一辆从该站的发车时间即可，换乘时间忽略。
给定 qq 次询问，每次给定一个数 LjL_j，求 JOI 君最晚可以在什么时刻从公交站 1 出发，才能按时到达；若无法到达，输出 -1。

做法

我们要求在时间 tt 前到达每个点的最晚出发时间 stst，这里的 stst 指从起点的最晚出发时间。
我们按到达时间 yy 从小到大排序，这样枚举到的第 ii 个巴士一定是当前到达 bb 的最迟的巴士。
所以对于每一个点 jj，我们维护 pos[b]pos[b] 表示到达 bb 的时间序列，因为排序所以有序；ans[b]ans[b] 表示在某一时间之前能到达站点 bb 的最晚出发时间。
对于每一条巴士路径，我们在 aa 站点二分第一个小于等于 xx 时刻的最晚出发时间，如果它大于目前 bb 站点的最晚出发时间那就加上，否则这劣于答案对答案无贡献。（这是贪心的思想，最晚出发时间肯定是要尽可能的晚，所以我们取最大值，并且这一步保证了答案维度的升序）。
特别的，站点为起点的最晚出发时间就是每条从起点出发的巴士的出发时间。

Code

CPP
#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;
}

评论

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

正在加载评论...