首页 > 试题广场 >

选药

[编程题]选药
  • 热度指数：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} 的药品。
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-11-25 18:15:39
题目链接 选药 题目描述 小红拿到了 种药品，第 种药品的疼痛程度是 ，功效值是 。小红希望选择一种药品，在疼痛值不超过她的忍耐度 的情况下，功效值尽可能大。共有 次询问。 输入: 第一行一个正整数 ，代表药品数量。 接下来 行，每行两个正整数 。 第 行，一个正整数 ，代表询问次数。 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 小小
发表于 2025-11-25 10:06:19
考核知识点：排序、库函数二分核心在于处理查询。由于查询次数较多且查询范围较大，直接遍历所有药品会超时。因此，需要对药品数据进行预处理，容易想到前缀最大值预处理+二分查找。 n = int(input()) drugs = [] for i in range(n): a, b = map(int, 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 yyyyjjjjxxxx
发表于 2025-11-26 22:24:19
import java.util.StringTokenizer; import java.io.OutputStreamWriter; import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 拒绝无效加班的牛油果很认真
发表于 2025-11-25 17:26:57
题目大意有 n 种药品，每种药品有两个属性：疼痛值 a_i功效值 b_i有 q 次查询，每次给定一个忍耐度 x要求：在所有 疼痛值 ≤ x 的药品中，找出 功效值最大 的那个若不存在满足条件的药品，输出 -1 解题思路步骤 1：去重 & 保留最优对于相同的疼痛值 a，只保留功效值最大的那个（ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 WYYQFF
发表于 2025-11-26 12:08:09
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct good { int a,b; }; bool cmp(good A,good B 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 鱼很腾
发表于 2025-11-26 19:05:12
#include<unordered_map> #include<algorithm> #include<iostream> using namespace std; int main() { int n=0; cin>>n; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 登高客
发表于 2025-11-28 08:42:07
因为要选功效尽可能大的，而对于药品的选择，我可以选所有疼痛值<=疼痛忍耐度的药品，所以排序之后疼痛值从小到大遍历找到当前的最大功效，就是当前疼痛忍耐值能使用的最大功效的药品，最后用二分来快速定位 #include <bits/stdc++.h> using namespace s 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 AK0
发表于 2025-11-27 10:35:13
#include <bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector< 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
1条回答 58浏览

热门推荐

相关试题

选药

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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