未了(endless)([CCF] NOI Online 能力测试2 入门组第一题)

时间限制： 1.0 秒

空间限制： 256 MB

题目描述
由于触犯天神，Sisyphus 将要接受惩罚。

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

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

1.用 3 年走到位置 3。
2.受 ai=3 的魔法影响，回到了山底出发。
3.再用 3 年走到位置 3，然而因为是第二次到达，ai=3 的魔法不起作用。
4.用 2 年走到位置 5。
5.受 ai=5 的魔法影响，回到了山底出发。
6.用 66 年从山底走到了山顶。花费的总时间为 1414 年。

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

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

第二行 n 个整数。第 i 个整数 ai表示第 i 个魔法作用的位置。（1≤i≤n）

第三行一个整数 q 表示宙斯的询问个数。

接下来 q 行每行一个整数，第 i 行的整数 ti表示宙斯的第 ii 个询问。（1≤i≤q）

输出格式
输出 q 行，每行恰好一个整数，第 i 行的整数对应第 i 个询问的答案。（1≤i≤q）

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

样例1输入
3 6 3
3 5 1
4
1
3
4
5

样例1输出
0
1
2
-1

————————————————
因为选k个魔法时，选最大的k个Ai所需时间最长，所以先将{A}从大到小排序，
最后二分答案
//PS:虽然nq<2³¹，但vti>2³¹所以要开long long。
代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(long long a,long long b)
{
	return a>b;
}
long long n,L,v,q;
long long mag[200010];
long long gs[200010];
int main()
{
	freopen("endless.in","r",stdin);
	freopen("endless.out","w",stdout);
	scanf("%lld%lld%lld",&n,&L,&v);
	for(long long i=1;i<=n;i++)
	scanf("%lld",&mag[i]);
	stable_sort(mag+1,mag+n+1,cmp);
	for(long long i=2;i<=n;i++)
	mag[i]+=mag[i-1]; 
	scanf("%lld",&q);
	for(long long i=1;i<=q;i++)
	{
		long long t;
		long long jl;
		scanf("%lld",&t);
		jl=t*v;
		if(gs[t])
		{
			printf("%lld\n",gs[t]);
			continue;
		}
		gs[t]=-1;
		long long l=0,r=n,mid=(l+r)/2;
		while(l<=r)
		{
			if(L+mag[mid]>jl)
			{
				r=mid-1;
				gs[t]=mid;
			}
			else
			{
				l=mid+1;
			}
			mid=(l+r)/2;
		}
		printf("%lld\n",gs[t]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}