1 solutions
-
3
解析见代码
/*思路:先思考宙斯的最优解法,再二分查找答案*/ #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