这个题目名称十分诡异。

然后我可以提供两种做法，复杂度一样，都是
$O(nlog n)$

O(nlogn)的。

方法一

因为我们每一次使用魔法，就会让那个什么鬼畜的人物多走个
$a_i$

ai​天，所以就可以贪心，每一次只要取大的就可以了，然后因为每一次都要加在一起看看够不够，所以就可以二分了。

代码

#include<bits/stdc++.h> #define maxn 200001 using namespace std; int n,L,v,m,t; long long a[maxn],sum[maxn]; bool cmp(const int &x,const int &y){ return x>y; } int main(){ scanf("%d%d%d",&n,&L,&v); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; scanf("%d",&m); while(m--){ scanf("%d",&t); int l=-1,r=n+1,mid; while(l+1<r){    mid=(l+r)>>1; if(sum[mid]+L<=(long long)t*v)l=mid; else r=mid; } if(r>n)printf("-1n");//我TM考试的时候没有换行全0分,样例的-1在最后面没有测出来qwq else printf("%dn",r); } return 0; } 

方法二

因为每一次的查询的
$t$

t，如果
$t_1<t_2$

t1​<t2​则
$t_2$

t2​要选的魔法数量不会少于
$t_1$

t1​的魔法数量，这样我们就可以先把
$t$

t拍个序，然后要注意记住原来的顺序然后就是模拟了。

代码

#include<bits/stdc++.h> using namespace std; int n,m,l,v; int a[200001]; struct zj{ int t,num,ans; }t[200001]; bool cmp(const int &x,const int &y){ return x>y; } bool cmp1(const zj &x,const zj &y){ return x.t<y.t; } bool cmp2(const zj &x,const zj &y){ return x.num<y.num; } int main(){ scanf("%d%d%d",&n,&l,&v); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+1+n,cmp); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d",&t[i].t),t[i].num=i; sort(t+1,t+1+m,cmp1); int k=0; long long sum=l; for(int i=1;i<=m;i++){ while(k<=n&&sum<=(long long)t[i].t*v)sum+=a[++k]; if(sum<=(long long)t[i].t*v)t[i].ans=-1; else t[i].ans=k; } sort(t+1,t+1+m,cmp2); for(int i=1;i<=m;i++)printf("%dn",t[i].ans); return 0; } 

谢谢–zhengjun