题解 P6473 【[NOI Online #2 入门组]未了】

此题作为NOI Online#2的第一题算是很良心了。

题目传送门

$1.$关于魔法

由于第 $i$ 个魔法 $a_i$ 会让 Sisyphus 在爬山爬到 $a_i$ 这个位置的时候从头重新爬，所以它的作用就是让 Sisyphus 白白爬 $a_i$ 长的山。

又因为 Sisyphus 每年可以爬 $v$ 的长度，所以这个魔法的作用本质上是让 Sisyphus 白白浪费 $\dfrac{a_i}{v}$ 的时间。

所以，我们可以在读入的时候就将 $a_i$ 除以 $v$。

$2.$（本题考查点）最少需要施展的魔法数量

一个很自然的想法是：将代表魔法能力的数组（此时已经除以 $v$ 了）降序排列，从第一个开始一直往后加，直到这个和大于要求的时间，再输出加了多少个数。

但是，这么做会导致最后三个点完美 TLE 。

TLE 了怎么办？前缀和+二分帮您完美解决！

我们可以将这个数组降序排列后计算每一项的前缀和，再利用C++ STL中自带upper_bound来二分查找最小的满足要求的数。

激动人心的时刻到了！ 最后，上代码！

#include<bits/stdc++.h>
using namespace std;
double l,v,a[200005],s[200005],t,y;//l,v如题意；数组a是魔法强度；数组s是数组a降序排列后的前缀和
int n,i,ans;//n如题意
bool cmp(double r,double s){
    return r>s;
}//用于在sort函数中进行降序排列
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);//高科技，可以给cin,cout加速
    cin>>n>>l>>v;
    y=l/v;//计算 Sisyphus 原本上山需要的时间
    for(i=1;i<=n;i++){
        cin>>a[i];//输入魔法强度
        a[i]/=v;//把魔法强度转化为这个魔法能让 Sisyphus 白白浪费的时间
    }
    sort(a+1,a+n+1,cmp);//降序排列
    for(i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];//计算前缀和
    }
    cin>>q;
    while(q--){
        cin>>t;//对于每一次询问
        if(y>=t){//如果 Sisyphus 原本上山需要的时间就比宙斯想让他上山用的时间多
            cout<<0<<endl;//直接输出0
        }
        else if(s[n]+y<=t){//如果 Sisyphus 不可能用那么多时间上山
            cout<<-1<<endl;//输出-1
        }
        else{
            ans=upper_bound(s+1,s+n+1,t-y)-s;//在前缀和数组中二分查找最小的大于等于t-y（即 Sisyphus 需要多爬的时间）的数，记得减去数组头指针s
            cout<<ans<<endl;//输出查找的结果
            //可以简化为cout<<upper_bound(s+1,s+n+1,t-y)-s<<endl;
        }
    }
    return 0;//完结撒花～
}