首页 > 试题广场 >

选药

[编程题]选药
  • 热度指数：937 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了 种药品，第i种药品的疼痛程度是a_i，功效值是b_i。小红希望选择一种药品，在疼痛值不超过x的情况下功效值尽可能大。你能帮帮她吗？
共有q次询问。


输入描述:
第一行输入一个正整数 n(1\leq n \leq 10^5)，代表药品数量。
接下去  行，每行两个正整数 a_i, b_i(1\leq a_i, b_i \leq 10^9)，分别代表药品的疼痛程度以及功效值。
第 n+2 行，输入一个正整数 q (1\leq q \leq 2 \times 10^5)，代表询问次数。
接下去  行，每行一个正整数 x(1\leq x \leq 10^9)，代表询问的疼痛忍耐度。


输出描述:
对于每个询问，输出一行一个正整数代表在该疼痛忍耐度内，效果最好的药品的功效值是多少。特殊的，如果不存在这样的药品，则输出 -1。
示例1

输入

5
3 10
4 2
6 6
9 10
10 9
3
1
6
9

输出

-1
10
10

说明

第一个询问，疼痛忍耐度只有 \text 1，没有任何药品满足要求。
第二个询问，疼痛忍耐度是 \text 6，可以选择疼痛程度为 \text 3 功效值为 \text {10} 的药品。
第三个询问，疼痛忍耐度是 \text 9，可以选择疼痛程度为 \text 3 功效值为 \text {10} 的药品。
算法知识视频讲解
添加回答
牛客797778782号头像 牛客797778782号
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
 int n;
 cin>>n;
vector<pair<long long,long long>>v(n);
for(int i=0;i<n;i++){
 cin>>v[i].first>>v[i].second;
}
sort(v.begin(),v.end());
vector<long long>list(n),pre_max(n);
long long cutmax=-1;
for(int i=0;i<n;i++){
    list[i]=v[i].first;
    cutmax=max(cutmax,v[i].second);
    pre_max[i]=cutmax;
}
int q;
cin>>q;
while(q--){
    long long x;
    cin>>x;
    int left=0,right=n-1;
    int ans=-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(list[mid]<=x){
            ans=mid;
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    if(ans==-1){
        cout<<-1<<endl;
    }else{
        cout<<pre_max[ans]<<endl;
    }

}
return 0;
}
发表于 2025-12-04 18:07:26 回复(0)
提交观点

问题信息

难度：
1条回答 57浏览

热门推荐

相关试题

选药

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号