题目链接

选药

题目描述

小红拿到了 种药品，第 种药品的疼痛程度是 ，功效值是 。小红希望选择一种药品，在疼痛值不超过她的忍耐度 的情况下，功效值尽可能大。共有 次询问。

输入:

  • 第一行一个正整数 ，代表药品数量。
  • 接下来 行，每行两个正整数 。
  • 第 行，一个正整数 ，代表询问次数。
  • 接下来 行，每行一个正整数 ，代表该次询问的疼痛忍耐度。

输出:

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

解题思路

这是一个典型的、可以通过预处理来优化查询效率的问题。如果对每次查询都遍历所有药品，总复杂度为 ，可能会超时。

一个更高效的策略是先对数据进行排序，然后通过预计算来加速查询。具体方法是“排序 + 前缀最大值 + 二分查找”。

  1. 排序: 将所有药品按照疼痛程度 从小到大排序。这样，具有相似疼痛程度的药品会聚集在一起。

  2. 预处理: 在排序后的药品列表上，我们创建一个“前缀最大功效”数组，记为 。 存储的是从第 0 个到第 个药品中，功效值的最大值。这个数组可以通过一次 的遍历来生成：

  3. 查询: 对于每次询问的疼痛忍耐度 ，我们实际上是想在所有满足 的药品中找到最大的 。

    • 由于药品已经按 排序，所有满足条件的药品一定是列表中的一个前缀。
    • 我们可以使用二分查找来高效地确定这个前缀的范围。具体地，我们查找第一个疼痛程度大于 的药品的位置。假设这个位置的索引是 ，那么所有索引小于 的药品都满足 。
    • 要找的答案就是这个前缀中的最大功效值，而这正是我们预处理好的 。
    • 如果二分查找发现所有药品的疼痛程度都大于 （即 ），则说明没有满足条件的药品，输出 -1。

这种方法将查询的复杂度从 降低到了 。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Medicine {
    int p, e;
};

// 用于 sort 的比较函数
bool compareMedicines(const Medicine& a, const Medicine& b) {
    return a.p < b.p;
}

void solve() {
    int n;
    cin >> n;
    vector<Medicine> meds(n);
    for (int i = 0; i < n; ++i) {
        cin >> meds[i].p >> meds[i].e;
    }

    // 1. 按疼痛程度排序
    sort(meds.begin(), meds.end(), compareMedicines);

    // 2. 预处理前缀最大功效值
    vector<int> prefix_max_e(n);
    prefix_max_e[0] = meds[0].e;
    for (int i = 1; i < n; ++i) {
        prefix_max_e[i] = max(prefix_max_e[i - 1], meds[i].e);
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int pain_tolerance;
        cin >> pain_tolerance;

        // 3. 二分查找
        // 查找第一个疼痛程度 > pain_tolerance 的药品
        auto it = upper_bound(meds.begin(), meds.end(), pain_tolerance, 
            [](int val, const Medicine& med) {
                return val < med.p;
            });
        
        int idx = distance(meds.begin(), it);

        if (idx == 0) {
            // 没有药品的疼痛程度 <= pain_tolerance
            cout << -1 << endl;
        } else {
            // 答案是 [0, idx-1] 范围内的最大功效值
            cout << prefix_max_e[idx - 1] << endl;
        }
    }
}

int main() {
    // 提高 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

class Medicine {
    int p, e;
    public Medicine(int p, int e) {
        this.p = p;
        this.e = e;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Medicine[] meds = new Medicine[n];
        for (int i = 0; i < n; i++) {
            meds[i] = new Medicine(sc.nextInt(), sc.nextInt());
        }

        // 1. 按疼痛程度排序
        Arrays.sort(meds, (a, b) -> a.p - b.p);

        // 2. 预处理前缀最大功效值
        int[] prefixMaxE = new int[n];
        prefixMaxE[0] = meds[0].e;
        for (int i = 1; i < n; i++) {
            prefixMaxE[i] = Math.max(prefixMaxE[i - 1], meds[i].e);
        }

        int q = sc.nextInt();

        for (int i = 0; i < q; i++) {
            int painTolerance = sc.nextInt();

            // 3. 二分查找
            int low = 0, high = n - 1;
            int idx = -1; // 最后一个 p <= painTolerance 的药品索引
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (meds[mid].p <= painTolerance) {
                    idx = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }

            if (idx == -1) {
                System.out.println(-1);
            } else {
                System.out.println(prefixMaxE[idx]);
            }
        }
    }
}

from bisect import bisect_right

def solve():
    # 使用 input 进行输入
    n = int(input())
    
    meds = []
    for _ in range(n):
        p, e = map(int, input().split())
        meds.append((p, e))
        
    # 1. 按疼痛程度排序
    meds.sort()
    
    # 2. 预处理前缀最大功效值
    prefix_max_e = [0] * n
    prefix_max_e[0] = meds[0][1]
    for i in range(1, n):
        prefix_max_e[i] = max(prefix_max_e[i-1], meds[i][1])
        
    # 提取疼痛值列表用于二分查找
    pains = [med[0] for med in meds]
    
    q = int(input())
    
    for _ in range(q):
        pain_tolerance = int(input())
        
        # 3. 二分查找
        # 查找第一个疼痛程度 > pain_tolerance 的药品位置
        idx = bisect_right(pains, pain_tolerance)
        
        if idx == 0:
            # 没有药品的疼痛程度 <= pain_tolerance
            print(-1)
        else:
            # 答案是 [0, idx-1] 范围内的最大功效值
            print(prefix_max_e[idx - 1])

solve()

算法及复杂度

  • 算法：排序、前缀最大值、二分查找
  • 时间复杂度: ，其中 是药品数量， 是询问次数。 用于排序，预处理为 ，每次查询的二分查找为 。
  • 空间复杂度: ，用于存储药品信息和前缀最大功效数组。