ACM-ICPC-OJ训练营

问题 3198 --坐汽车

3198: 坐汽车

时间限制: 3 Sec 内存限制: 128 MB
提交: 0 解决: 3
[提交][状态][讨论版][命题人:]

题目描述

小劉乘坐的汽车在数线上从点 0 开往点 n 。在第 0 分钟，汽车从第 0 点开始行驶
在 0,a1,2,...,ak 点的直线上有 k+1 个标志，小劉知道汽车将分别在0,b1, b2,...,bk 分钟到达那里。序列 α和b与 ak=n 严格递增。

在任意两个相邻的标志牌之间，汽车以恒速行驶。小劉有 q 个查询:每个查询都是个整数 d ，小劉希望你输出汽车到达 d 点需要多少分钟，所有数字下取整

输入描述

第一行包含一个整数 t( 1<t<1e4)。( 1<t< 1e4)- 测试用例的数量。
每个测试用例的第一行分别包含三个整数 n、k和q,( k<=n< =1e9 ;1≤ k,q≤ 1e5)--最终目的地、小劉知道时间的点数以及査询次数。
每个测试用例的第二行包含 k 个整数 ai( 1≤ai≤n ; ai< ai+1 ，每1<i<k-l;ak=n )。
每个测试用例的第三行包含 k 个整数 bi(1≤bi≤1e9; bi<bi+1 ，每1≤i≤ k-1 个整数)。
接下来的每行 q 都包含一个整数 d(0<d<n )- Timur 询问分钟经过的距离。所有测试用例中 k的总和不超过 1e5所有测试用例中 q 的总和不超过 1e5

输出描述

对于每个查询，输出一个整数--汽车到达点d前的分数钟数

样例输入

4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5

样例输出

提示

在第一个测试案例中，汽车在 10 分钟内从 0 点行驶到 10 点，

因此速度为每分钟 1个单位:

在 0 点，时间为 0分钟:

在6 点，时间为 6 分钟。

在7 点，时间为 7 分钟。

第二个测试案例中，在 0 和 4 点之间，汽车以每分钟 1 个单位的速度行驶;在 4 和10 点之间，汽车以每分钟 2 个单位的速度行驶:

在 6 点，时间为 5 分钟。

在4 点，时间为 4 分钟。

在2点，时间为 2 分钟。

在7点，时间为 5.5 分钟，因此答案为5。

在第四个测试用例中，汽车每分钟的行驶速度为 1.2 个单位，因此查询的答案为:

在2点，时间为 1.66...分钟，因此答案为 12 点，

在6点，时间为 5 分钟。

在 5 点，时间为 4.16...分钟，故答案为 4。

来源

23软三刘震峰

[提交][状态]