题目大意

• 有 n 种药品，每种药品有两个属性：疼痛值 a_i功效值 b_i
• 有 q 次查询，每次给定一个忍耐度 x
• 要求：在所有 疼痛值 ≤ x 的药品中，找出 功效值最大 的那个
• 若不存在满足条件的药品，输出 -1

解题思路

步骤 1：去重 & 保留最优

• 对于相同的疼痛值 a，只保留功效值最大的那个（因为更优）
• 可用 Map<Integer, Integer> 实现：map.put(a, max(map.get(a), b))

步骤 2：按疼痛值排序

• 将所有不同的 a 值提取出来并升序排列（TreeSet）

步骤 3：预处理前缀最大功效值

• 因为疼痛值已排序，我们可以计算 前缀最大功效值即：对于每个疼痛值 a[i]，记录所有 ≤ a[i] 的药品中的最大功效值
• 这样，任意 x 查询时，只需找到 最大的 a[i] ≤ x，其对应的前缀最大值即为答案

步骤 4：二分查找

• 在有序的疼痛值数组中，使用 二分查找 找到最后一个 ≤ x 的位置
• 时间复杂度：O(log n) 每次查询

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

public class Main {

	private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	private static StreamTokenizer st = new StreamTokenizer(reader);
	private static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

	private static int n, q;

	private static Map<Integer, Integer> map = new HashMap<>();
	private static TreeSet<Integer> set = new TreeSet<>();
	private static List<Integer> list;

	public static void main(String[] args) throws IOException {
		while (st.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) st.nval;

			for (int i = 0; i < n; i++) {
				st.nextToken();
				int a = (int) st.nval;
				st.nextToken();
				int b = (int) st.nval;
				set.add(a);
				map.put(a, Math.max(map.getOrDefault(a, 0), b));
			}
			list = new ArrayList<>(set);
			int tempMax = 0;
			for (Integer key : list) {
				tempMax = Math.max(tempMax, map.get(key));
				map.put(key, tempMax);
			}

			st.nextToken();
			q = (int) st.nval;

			while (q-- > 0) {
				st.nextToken();
				int x = (int) st.nval;
				int l = 0;
				int r = list.size() - 1;
				int ans = -1;
				while (l <= r) {
					int mid = (r - l) / 2 + l;
					if (list.get(mid) <= x) {
						ans = map.get(list.get(mid));
						l = mid + 1;
					} else {
						r = mid - 1;
					}
				}
				writer.println(ans);
			}

		}
		writer.flush();
		writer.close();
		reader.close();
	}

}