【二分】 [NOI Online #2 入门组]未了

入门组]未了"/>

【二分】 [NOI Online #2 入门组]未了

L i n k Link Link

l u o g u P 6473 luogu\ P6473 luogu P6473

D e s c r i p t i o n Description Description

由于触犯天神， S i s y p h u s Sisyphus Sisyphus 将要接受惩罚。
宙斯命 S i s y p h u s Sisyphus Sisyphus 推一块巨石上长度为 L L L 的山坡。 S i s y p h u s Sisyphus Sisyphus 匀速向上推的速度为每年 v v v 的长度（由于是匀速，故经过 1 2 \frac{1}{2} 21​ 年将能向上推 v 2 \frac{v}{2} 2v​
​
的长度）。然而，宙斯并不希望 S i s y p h u s Sisyphus Sisyphus太快到达山顶。宙斯可以施展 n n n 个魔法，若宙斯施展第 i i i 个魔法 ( 1 ≤ i ≤ n 1\leq i \leq n 1≤i≤n) ，则当 S i s y p h u s Sisyphus Sisyphus 第一次到达位置 a i a_i ai​
​
时，他将会同巨石一起滚落下山底，并从头推起。（滚落的时间忽略不计，即可看作第一次到达位置 a i a_i ai​后 S i s y p h u s Sisyphus Sisyphus 立即从山底重新出发）

例如宙斯施用了 a i = 3 a_i=3 ai​=3 和 a i = 5 a_i=5 ai​=5
​
=5 的两个魔法。 S i s y p h u s Sisyphus Sisyphus 的速度 v = 1 v=1 v=1 ，山坡的长度 L = 6 L = 6 L=6，则他推石上山过程如下：

用 3 3 3 年走到位置 3 3 3。

受 a i = 3 a_i=3 ai​=3 的魔法影响，回到了山底出发。

再用 3 3 3 年走到位置 3 3 3，然而因为是第二次到达， a i = 3 a_i=3 ai​=3 的魔法不起作用。

用 2 2 2 年走到位置 5 5 5。

受 a i = 5 a_i=5 ai​=5 的魔法影响，回到了山底出发。

用 6 6 6 年从山底走到了山顶。花费的总时间为 14 14 14 年。

现在，宙斯有 q q q 个询问。对于第 i i i 个询问 t i t_i ti​，宙斯想知道，他最少需要施展多少个魔法才能使 S i s y p h u s Sisyphus Sisyphus 到达山顶所用的年数大于 t i t_i ti​
​

I n p u t Input Input

第一行三个整数 n , L , v n,L,v n,L,v 分别表示魔法的种类数，山坡的长度， S i s y p h u s Sisyphus Sisyphus 的速度。

第二行 n n n 个整数。第 i i i 个整数 a i a_i ai​​, 表示第 i i i 个魔法作用的位置。 ( 1 < i < n ) (1<i<n) (1<i<n)
第三行一个整数 q q q 表示宙斯的询问个数。

接下来 q q q 行每行一个整数，第 i i i 行的整数 t i t_i ti​​, 表示宙斯的第 i i i 个询问。

O u t p u t Output Output

输出 q q q 行，每行恰好一个整数，第 i i i 行的整数对应第 i i i 个询问的答案。 ( 1 ≤ i ≤ q ) (1 \leq i\leq q) (1≤i≤q)

如果宙斯无论如何都不能使 S i s y p h u s Sisyphus Sisyphus 使用的年数大于 t i t_i ti​，请输出 − 1 -1 −1

S a m p l e Sample Sample I n p u t Input Input

3 6 3
3 5 1
4
1
3
4
5

S a m p l e Sample Sample O u t p u t Output Output

0
1
2
-1

H i n t Hint Hint

不使用任何魔法， S i s y p h u s Sisyphus Sisyphus 需要 2 2 2 年走上山顶。
使用魔法 2 2 2 ， S i s y p h u s Sisyphus Sisyphus 需要 11 3 \frac{11}{3} 311​ 年走上山顶。
用时 5 3 \frac{5}{3} 35​ 年走到魔法 2 2 2 的位置并滚落下山
再用时 6 3 = 2 \frac{6}{3}=2 36​=2 年走到山顶
使用魔法 1 , 2 1,2 1,2 ， S i s y p h u s Sisyphus Sisyphus 需要 14 3 \frac{14}{3} 314​ 年走上山顶。
宙斯不能使 S i s y p h u s Sisyphus Sisyphus 用大于 5 5 5 年的时间走上山顶。

T r a i n Train Train o f of of T h o u g h t Thought Thought

很容易想到，肯定是越往后的魔法越优，因此将魔法倒序
然后求出前缀和，很容易想到一个个比较，但是这样会炸掉
因此我们要使用二分
求出第一个比读入的时间大的位置（即为答案）
还有一些特殊情况需要特判一下

记得用 d o u b l e double double

C o d e Code Code

#include<algorithm>
#include<iostream>
#include<cstdio>using namespace std;double l, v, a[200005], s[200005];
long long n;bool cmp(double i, double j)
{return i > j;}//降序排序int main()
{scanf("%lld%lf%lf", &n, &l, &v);s[0] = l / v;for (int i = 1; i <= n; ++i)scanf("%lf", &a[i]);sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; ++i)s[i] = s[i - 1] + double(a[i]) / v;//求前缀和int q;scanf("%d", &q);while(q--){int x;scanf("%d", &x);if (x > s[n]) printf("-1\n");else {int l = 0, r = n, ans = 0;while (l <= r){int mid = (l + r) / 2;if (s[mid] > x) r = mid - 1, ans = mid;else l = mid + 1;}//二分模板printf("%d\n", ans);} }return 0;
}