题解 | 选药

因为要选功效尽可能大的，而对于药品的选择，我可以选所有疼痛值<=疼痛忍耐度的药品，所以排序之后疼痛值从小到大遍历找到当前的最大功效，就是当前疼痛忍耐值能使用的最大功效的药品，最后用二分来快速定位

#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;
}