题解 | 选药

#include <stdio.h>
#include<stdlib.h>
typedef struct {
    int a;
    int b;
}Drag;
int cmp(const void *a,const void *b){
    return ((Drag*)a)->a - ((Drag*)b)->a;
}
int main() {
    int i=0;
    int n;
    scanf("%d",&n);
    Drag *drag=(Drag*)malloc(n*sizeof(Drag));
    
    //初始
    for(;i<n;i++){
        scanf("%d %d",&drag[i].a,&drag[i].b);
    }
    
    //排序
    qsort(drag,n,sizeof(Drag),cmp);
    
    int *max_b=(int *)malloc(sizeof(int)*n);
    max_b[0]=drag[0].b;
    for(i=1;i<n;i++){
        if(max_b[i-1] < drag[i].b){
            max_b[i]=drag[i].b;
        }
        else{
            max_b[i]=max_b[i-1];
        }
    }

    //询问
    int ask;
    scanf("%d",&ask);
    while(ask-->0){
        int x;
        scanf("%d",&x);
        //查找
        int l=0;
        int r=n-1;
        int result=-1;
        while(l <= r){
            int mid=(l+r)/2;
            if(x >= drag[mid].a){
                result=max_b[mid];
                l=mid+1;
            }else{
                r=mid-1;
            }
        }printf("%d\n",result);
    }
    return 0;
}