5086.等公交车

时间限制:1s 内存限制:128MB

小G和朋友约好了时间出去玩,他选择坐公交车去找对方。

早早的便来到了公交站牌处开始了等公交车,但公交车却迟迟不来,终于在他濒临爆发的时候,公交车终于缓缓开来。开心的和朋友会合后,他们便开始了一天的玩乐。回到家后,小G还是对于等公交车耿耿于怀,现已知每天都会发出$m$辆公交车,在手机上它可以查出这$m$辆公交车的发车时刻第$t_i$分钟,并且他还知道所有的站点信息,总共有$n$个公交车站点,以及每个站点距离发车点的距离$d_i$米。已知公交车的速度为$1$米/分钟,以及发车点和所有的站点都在一条直线上,每次公交车从发车点出发后,依次经过每个站点。他想知道能否设计一个程序,当每次一个乘客在某个时刻时到达某个站点时,可以直接告诉他需要等待的时间?

例:如果当前有$3$辆公交车,发车时刻分别为$1,3,5$,当前有$2$个站点,距离发车点分别为$2,4$,则若一个乘客在时刻$4$时来到了第$1$个站点,则第一辆公交车会在时刻$3$到达一号站点,该乘客无法乘上此辆车,第二辆公交车会在时刻$5$到达一号站点,该乘客需要等待$1$分钟来乘上该辆公交车。

输入格式(从终端/标准输入读取)

第一行两个个正整数,表示$n,m$.
第二行$n$个正整数,表示$n$个站点距离发车点的距离$d_i$.(数据保证$d_i$递增)
第三行$m$个正整数,表示$m$辆公交车的发车时刻$t_i$.(数据保证$t_i$递增)
第四行一个正整数$Q$,表示接下来的询问个数。
接下来$Q$行,每行两个正整数$t,x$,表示该乘客在时刻$t$时来到了$x$号站点。

输出格式(输出至终端/标准输出)

$Q$行,每行一个整数表示需要等待的时间,若该乘客任何公交车都无法乘上,请输出$TNT$

输入样例

复制
2 3
2 4
1 3 5
5
3 1
4 1
5 1
8 2
10 2
 · \n
 · \n
 · · \n
 \n
 · \n
 · \n
 · \n
 · \n
  · \n

输出样例

复制
0
1
0
1
TNT
 \n
 \n
 \n
 \n
   \n

说明

对于100%的数据,$1 \leq n,m, q \leq 10^5, 1\leq l_i,t_i\leq 2\times 10^9$

来源: 河南萌新联赛2024第(六)场

提交题解

Please login first.

© 2025 FAQs