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。
3 6 3
3 5 1
4
1
3
4
5
0
1
2
-1

推荐代码 查看3951 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$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

竞赛编号 竞赛名称 竞赛时间 访问比赛