1 条题解
-
0
对于每次询问,只要让增加的学习量 满足
同时要让使用的魔法次数最少,考虑贪心,优先释放增加量大的魔法。可以将所有魔法根据增加量降序排序后进行前缀和,即可得到释放 个魔法最多能让队友要学的知识增加
对于每次询问,只要二分找到满足 的最小下标 即为答案,总体时间复杂度 O(nlogn)
#include<iostream> #include<algorithm> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; using ll = long long; const int N = 2e5 + 10; #define int ll int a[N]; bool cmp(int a, int b) { return a > b; } signed main() { IOS int n, L, v; cin >> n >> L >> v; for (int i = 1;i <= n;i++) { cin >> a[i]; } sort(a + 1, a + n + 1, cmp); for (int i = 1;i <= n;i++) { a[i] += a[i - 1]; } int mx = a[n]; //最多可以增加的知识 int q; cin >> q; while (q--) { int t; cin >> t; int d = t * v - L + 1; //至少应该增加的知识 if (d > mx) { cout << -1 << endl; continue; } int ans = lower_bound(a, a + n + 1, d) - a;//注意从a[0]找起 cout << ans << endl; } return 0; }
- 1
信息
- ID
- 77
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者