1 solutions

  • 3
    @ 2024-7-16 13:19:15

    解析见代码

    /*思路:先思考宙斯的最优解法,再二分查找答案*/ 
    
    #include<bits/stdc++.h>
    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]; //使用第i个魔法所需的路程 
    	cin>>q;
    	for(long long i=0;i<q;i++)//询问次数 
    	{
    		cin>>t;//每一次询问 
    		long long s=1ll*t*v;//1LL会在运算时把后面的临时数据扩容成long long类型,再在赋值给左边时转回int类型。 
    		long long ans=upper_bound(sum,sum+n+1,s)-sum;//二分查找第一个大于该路程的魔法 (因为sum[i]就是使用i个魔法,所以直接返回i) 
    		if(ans==n+1)
    			cout<<"-1"<<endl;//如果找不到,说明不行 
    		else 
    			cout<<ans<<endl;//否则输出 
    	}	
    	return /*164*/0; 
     }
    
    • 1

    Information

    ID
    5504
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    3
    Tags
    # Submissions
    54
    Accepted
    14
    Uploaded By