题解 | 选药
选药
https://www.nowcoder.com/practice/f55f93b3560248f4b4532490206df398
因为要选功效尽可能大的，而对于药品的选择，我可以选所有疼痛值<=疼痛忍耐度的药品，所以排序之后疼痛值从小到大遍历找到当前的最大功效，就是当前疼痛忍耐值能使用的最大功效的药品，最后用二分来快速定位
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int main() {
int n, mx = -1;
cin >> n;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
v.push_back({a, b});
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) {
mx = max(mx, v[i].second);
v[i].second = mx;
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
int l = -1, r = v.size();
while (l + 1 < r) {
int mid = l + r >> 1;
if (v[mid].first <= x) l = mid;
else r = mid;
}
if (l == -1 || v[l].first > x) cout << -1 << '\n';
else cout << v[l].second << '\n';
}
return 0;
}
帆软软件公司氛围 105人发布