未了（endless）

一、题目描述

由于触犯天神，Sisyphus 将要接受惩罚。
宙斯命 Sisyphus 推一块巨石上长度为的山坡。Sisyphus 匀速向上推的速度为每年的长度（由于是匀
速，故经过1/2年将能向上推v/2的长度）。然而，宙斯并不希望 Sisyphus 太快到达山顶。宙斯可以施展n个魔法，

若宙斯施展第个魔法（1 <= i <= n ），则当 Sisyphus 第一次到达位置时，他将会同巨石一起滚落下山底，并从头推起。

（滚落的时间忽略不计，即可看作第一次到达位置后 Sisyphus 立即从山底重新出发）

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

1. 用3年走到位置3。
2. 受 a[i] = 3的魔法影响，回到了山底出发。
3. 再用3年走到位置3，然而因为是第二次到达， a[i] = 3的魔法不起作用。
4. 用2年走到位置5。
5. 受 a[i] = 5的魔法影响，回到了山底出发。
6. 用6年从山底走到了山顶。花费的总时间为14年。
现在，宙斯有q个询问。对于第 i个询问 t[i]，宙斯想知道，他最少需要施展多少个魔法才能使 Sisyphus 到达山顶所用的年数大于 t[i]
输入格式
第一行三个整数分别表示魔法的种类数，山坡的长度，Sisyphus 的速度。
第二行n个整数。第i个整数a[i]表示第 i 个魔法作用的位置。（ 1 <= i <= n）
第三行一个整数q表示宙斯的询问个数。
接下来q行每行一个整数t[i]，第i行的整数 t[i] 表示宙斯的第i个询问。（1 <= i <= q ）
输出格式
输出q行，每行恰好一个整数，第 i 行的整数对应第 i 个询问的答案。（1 <= i <= q ）
如果宙斯无论如何都不能使 Sisyphus 使用的年数大于，请输出。
样例输入
3 6 3
3 5 1
4
1
3
4
5
样例输出

0

1

2

-1

样例解释

1. 不使用任何魔法，Sisyphus 需要年走上山顶。
2. 使用魔法 ，Sisyphus 需要年走上山顶。（用时年走到魔法的位置并滚落下山，再用时
年走到山顶）
3. 使用魔法，Sisyphus 需要年走上山顶。
4. 宙斯不能使 Sisyphus 用大于年的时间走上山顶。

二、解题思路

输入魔法的位置 a[i]， 按降序（从大到小）排序

1、把n个魔法存到year_num数组第n个位置

2、看year_num[n]（所有魔法都用）能不能保证比宙斯想要的年份 （t[i]）要大，如果所有魔法都用还比不上宙斯查询的 t[i] ， 输出-1 

3、如果能比宙斯查询的年份要大，输出要用几个魔法

三、代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,l,v,a[200005],q,t[200005];
double year_num[200005];

bool cmp(int x, int y){
    return x > y;
}

int main(){
    //freopen("endless.in","r",stdin);
    //freopen("endless.out","w",stdout);
    cin >> n >> l >> v;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    sort(a,a+n,cmp);//降序排列 
    cin >> q;
    for(int i = 0;i < q;i++){
        cin >> t[i];
    }
    year_num[0] = (double)l/v;//如果1个魔法都不用的话，就是山坡的高度除以每年爬的速度 
    for(int j = 1;j <= n;j++){
        year_num[j] = year_num[j-1] + (double)a[j-1]/v;
    }
    int j = 0, i = 0;//i待会要作为t数组的下标，所以不能作为year_num的下标
    //所以加了个j，如果这次year_num[j]比t[i]小的话，j++(判断year_num的下一个)，而i不能++ 
    while(i < q){
        if(year_num[n] <= t[i]){//所有魔法都用上也不能比查询的年数要大 
            cout << -1 << endl;//不可能达到宙斯的查询，输出1 
            i++;//下一个循环该判断下一个查询的年数了 
            continue;
        }
        if(year_num[j] > t[i]){//如果只用j个魔法就比t[i]大了 
            cout << j << endl;//输出j 
            i++;//判断下一个查询 
        }else{
            j++;//只用j个魔法不行，多用一个魔法试试 -> j++ 
        }
        i = 0;
        j = 0; 
    }
    return 0;
}