题解 | [JSOI2007]建筑抢修

import java.io.*;
import java.util.*;

/**
 * 维修建筑最大数量问题
 * 核心策略：贪心（按时限排序）+ 最大堆（替换最长耗时）
 */
public class Main {
     public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        // 存储每个建筑的维修耗时t和报废时限d
        int[][] buildings = new int[n][2];

        for (int i = 0; i < n; i++) {
            String[] numStr = br.readLine().split("\\s+");
            buildings[i][0] = Integer.parseInt(numStr[0]);
            buildings[i][1] = Integer.parseInt(numStr[1]);
        }
        // 按报废时限d_i升序排序（优先处理时限早的）
        Arrays.sort(buildings, (a, b) -> a[1] - b[1]);

        // 初始化最大堆（存储已选建筑的耗时，优先弹出最大值）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        long total = 0; // 当前累计维修时间

        for (int[] b : buildings) {

            int t = b[0];
            int d = b[1];
            // 加入当前建筑，累计时间
            maxHeap.add(t);
            total += t;
            // 若累计时间超过当前建筑的时限，移除耗时最长的建筑
            if (total > d) {
                int removeT = maxHeap.poll();
                total -= removeT;
            }

        }
        // 堆的大小即为最多可维修的建筑数量
        out.println(maxHeap.size());

        out.flush();
        out.close();
        br.close();
    }
}