题解 | 选药

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin>>n;
vector<pair<int,int>>medicines(n);
for(int i=0;i<n;i++){
    cin>>medicines[i].first>>medicines[i].second;
}
sort(medicines.begin(),medicines.end());

vector<int>prefix_max(n);
prefix_max[0]=medicines[0].second;
for(int i=1;i<n;i++){
    prefix_max[i]=max(prefix_max[i-1],medicines[i].second);
}
int q;
cin>>q;
while(q--){
int x;
cin>>x;
int left=0;
int right=n-1;
int mid;
int pos=-1;
while(left<=right){
    mid=(left+right)/2;
    if(medicines[mid].first<=x){
        pos=mid;
        left=mid+1;
    }
    else{
    right=mid-1;
    }
}
if(pos==-1)cout<<-1<<endl;
else cout<<prefix_max[pos]<<endl;
}
    return 0;
}