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

$Link$Link

$luogu\ P6473$luogu P6473

$Description$Description

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

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

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

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

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

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

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

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

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

$Input$Input

第一行三个整数 $n,L,v$n,L,v 分别表示魔法的种类数，山坡的长度，$Sisyphus$Sisyphus 的速度。

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

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

$Output$Output

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

如果宙斯无论如何都不能使 $Sisyphus$Sisyphus 使用的年数大于 $t_i$ti​，请输出 $-1$−1

$Sample$Sample $Input$Input

3 6 3
3 5 1
4
1
3
4
5

$Sample$Sample $Output$Output

0
1
2
-1

$Hint$Hint

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

$Train$Train $of$of $Thought$Thought

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

记得用$double$double

$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;
}