endless]"/>
未了[endless]
未了[endless]
题目描述
由于触犯天神,Sisyphus 将要接受惩罚。
宙斯命 Sisyphus 推一块巨石上长度为 L 的山坡。Sisyphus 匀速向上推的速度为每年 v 的长度(由于 是匀速,故经过 12 年将能向上推 v2 的长度)。然而,宙斯并不希望 Sisyphus 太快到达山顶。宙斯可 以施展 n 个魔法,若宙斯施展第 i 个魔法(1 ≤ i ≤ n),则当 Sisyphus 第一次到达位置 ai 时,他 将会同巨石一起滚落下山底,并从头推起。(滚落的时间忽略不计,即可看作第一次到达位置 ai 后 Sisyphus 立即从山底重新出发)
例如宙斯施用了 ai = 3 与 ai = 5 的两个魔法。Sisyphus 的速度 v = 1,山坡的长度 L = 6,则他 推石上山过程如下:
- 用 3 年走到位置 3。
- 受 ai = 3 的魔法影响,回到了山底出发。
- 再用 3 年走到位置 3,然而因为是第二次到达,ai = 3 的魔法不起作用。
- 用 2 年走到位置 5。
- 受 ai = 5 的魔法影响,回到了山底出发。
- 用 6 年从山底走到了山顶。花费的总时间为 14 年。
现在,宙斯有 q 个询问。对于第 i 个询问 ti ,宙斯想知道,他最少需要施展多少个魔法才能使 Sisyphus 到达山顶所用的年数大于 ti 。
输入格式
第一行三个整数 n, L, v 分别表示魔法的种类数,山坡的长度,Sisyphus 的速度。
第二行 n 个整数。第 i 个整数 ai 表示第 i 个魔法作用的位置。(1 ≤ i ≤ n)
第三行一个整数 q 表示宙斯的询问个数。
接下来 q 行每行一个整数,第 i 行的整数 ti 表示宙斯的第 i 个询问。(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
样例1解释
-
不使用任何魔法,Sisyphus 需要 2 年走上山顶。
-
使用魔法 2 ,Sisyphus 需要 113 年走上山顶。(用时 53 年走到魔法 2 的位置并滚落下山,再用时 63 = 2 年走到山顶)
-
使用魔法 1,2 ,Sisyphus 需要 143 年走上山顶。
-
宙斯不能使 Sisyphus 用大于 5 年的时间走上山顶。
数据范围与提示
对于测试点 1 ∼ 8:n = 1。
对于测试点 9 ∼ 12:n = 2。
对于测试点 13 ∼ 17:n, q ≤ 1000。
对于所有测试点:1 ≤ n, q ≤ 2 × 105,1 ≤ v ≤ L ≤ 109,1 ≤ ai < L,1 ≤ ti ≤ 109。
数据保证 ai 两两不同。
解题思路
- 将所有ai排序,维护ai的前缀和[不懂前缀和的来这里前缀和博客
- 对于每个询问,二分第一个最大的若干个ai的前缀和加入总路程之后能满足询问要求的位置
核心代码
#include<iostream>
#include<algorithm>
using namespace std;
long long n,l,v,q,t,a[200010],sum[200010];
int main()
{cin>>n>>l>>v;for(long long i=0;i<n;i++) cin>>a[i];sum[0]=l;sort(a,a+n);reverse(a,a+n);for(long long i=0;i<n;i++) sum[i+1]=sum[i]+a[i];cin>>q;for(long long i=0;i<q;i++){cin>>t;long long s=1ll*t*v;long long ans=upper_bound(sum,sum+n+1,s)-sum;if(ans==n+1)cout<<"-1"<<endl;else cout<<ans<<endl;} return 0;}
出处:中国计算机学会
此博客为转载文章
非原创
有问题可以在下边提出来记得
@Y_bluefat
更多推荐
未了[endless]
发布评论