Problem 3951 --5-1 爬山坡3951: 5-1 爬山坡
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$2$ |
正确数量 |
$1$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
当前分类(单击移除)：
单击选择分类：
小A做了一个小游戏。玩家在游戏中需要推一块巨石到长度为L的山坡顶部。玩家向上推的速度为每天v的长度（由于是匀速，故经过半天可以上推v/2的长度）。然而，小A并不希望这个游戏太快结束，所以他打算设置一些陷阱进行干扰。小A可以设置n个陷阱，位置位于a1,a2,…,an，每个陷阱只能被触发一次。如果玩家触及到第i个陷阱(1≤i≤n)，则当你第一次到达位置ai时，将会和巨石一起滚落下山底，并从头推起。（滚落的时间忽略不计，即可看作第一次到达位置ai后立即从山底重新出发）
例如小A设置了位于a1=3和a2=5 的两个陷阱。玩家的速度v=1，山坡的长度L=6，则他推石上山过程如下：
1、用3 天走到位置3，受到a1=3的陷阱影响，回到了山底出发。
2、再用3天走到位置3，然而因为是第二次到达，a1=3的陷阱不起作用。
3、用 2 天走到位置 5，受到a2=5的陷阱影响，回到了山底出发。
4、用6天从山底走到了山顶。花费的总时间为14天。
现在，小A有q个询问。对于第j个询问tj，小A想知道，他最少需要选择多少个陷阱，才能使玩家到达山顶所用的天数大于tj。
第一行三个整数n,L,v分别表示陷阱的个数，山坡的长度和玩家的速度。(1≤v≤L≤1e9)
第二行n个整数,中间以空格隔开。第i个整数ai表示可以设第i个陷阱的位置。(1≤i≤n≤200,000)
第三行一个整数q表示小A的询问个数。
接下来q行每行一个整数，第j行的整数tj表示小A第j个询问。(1≤j≤q≤200,000, 1≤tj≤1e9)
输出q行，每行恰好一个整数，第j行的整数对应第j个询问的答案。(1≤j≤q)
如果布置所有的n个陷阱也不能使玩家到达山顶所用的天数大于tj，请输出−1。
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$58 $ms]
|
AOJ大管家
|
803190
|
2021-12-24 20:02:47 |
| 内存最少[$5212 $KB]
|
AOJ大管家
|
803190 |
2021-12-24 20:02:47 |
| 第一AC |
AOJ大管家 |
803190
|
2021-12-24 20:02:47 |
| 第一挑战 |
AOJ大管家
|
803117 |
2021-12-24 18:49:44 |
赛题来源/所属竞赛
1E
N/A