题目链接

PEEK115 [JSOI2007]建筑抢修

题目描述

共有 座建筑受损。维修第 座建筑需要 秒，且必须在 秒内完成（含第 秒）。维修工同一时刻只能维修一座建筑，请求出最多能成功维修的建筑数量。

解题思路

这是一个典型的贪心问题，可以使用优先队列（大顶堆）来解决。

核心思想是：总是优先处理截止日期早的建筑，并随时准备用耗时短的新任务替换已选的耗时长的任务，以节省时间。

具体步骤如下：

  1. 排序：将所有建筑按照其截止日期 从小到大进行排序。这确保我们总是先考虑最紧急的维修任务。
  2. 遍历与决策：我们按排序后的顺序遍历每个建筑，并维护一个当前已花费的总时间 currentTime 和一个大顶堆 pq。大顶堆用来存储我们已决定要维修的建筑所花费的时间。
    • 对于当前遍历到的建筑（耗时为 ，截止日期为 ）：

      • 情况一：可以直接维修

        如果 currentTime + ，说明时间充裕，我们可以直接接下这个维修任务。此时，我们将 加入 currentTime，并将 push进大顶堆 pq。

      • 情况二：时间不足，考虑替换（反悔）

        如果 currentTime + ，我们不能直接维修它。但可以考虑一个“反悔”策略：查看大顶堆的堆顶元素（即已选任务中的最长耗时 max_t）。如果当前任务的耗时 小于 max_t，那么用当前任务替换掉那个最耗时的任务是更优的。

        • 替换操作：从 pq 中弹出 max_t，然后将新的 推入。同时更新总耗时 currentTime = currentTime - max_t + t。这样做节省了 max_t - t 的时间，为后续任务创造了更多可能性，并且维修的建筑总数不变。
        • 如果 不小于 max_t，则替换没有意义，我们直接放弃当前建筑。
  3. 最终结果：遍历完所有建筑后，大顶堆 pq 的大小就是最多能维修的建筑数量。

代码

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

using namespace std;

struct Building {
    int t, d;
};

bool compareBuildings(const Building& a, const Building& b) {
    return a.d < b.d;
}

int main() {
    int n;
    cin >> n;
    vector<Building> buildings(n);
    for (int i = 0; i < n; ++i) {
        cin >> buildings[i].t >> buildings[i].d;
    }

    sort(buildings.begin(), buildings.end(), compareBuildings);

    priority_queue<int> pq; // 大顶堆
    long long currentTime = 0;

    for (int i = 0; i < n; ++i) {
        if (currentTime + buildings[i].t <= buildings[i].d) {
            currentTime += buildings[i].t;
            pq.push(buildings[i].t);
        } else if (!pq.empty() && pq.top() > buildings[i].t) {
            currentTime -= pq.top();
            pq.pop();
            currentTime += buildings[i].t;
            pq.push(buildings[i].t);
        }
    }

    cout << pq.size() << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Comparator;

class Building {
    int t, d;

    public Building(int t, int d) {
        this.t = t;
        this.d = d;
    }
}

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

        Arrays.sort(buildings, Comparator.comparingInt(b -> b.d));

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // 大顶堆
        long currentTime = 0;

        for (int i = 0; i < n; i++) {
            if (currentTime + buildings[i].t <= buildings[i].d) {
                currentTime += buildings[i].t;
                pq.add(buildings[i].t);
            } else if (!pq.isEmpty() && pq.peek() > buildings[i].t) {
                currentTime -= pq.poll();
                currentTime += buildings[i].t;
                pq.add(buildings[i].t);
            }
        }

        System.out.println(pq.size());
    }
}

import heapq

def main():
    n = int(input())
    buildings = []
    for _ in range(n):
        buildings.append(list(map(int, input().split())))

    # 按截止日期排序
    buildings.sort(key=lambda x: x[1])

    pq = []  # 小顶堆，存入负数模拟大顶堆
    current_time = 0

    for t, d in buildings:
        if current_time + t <= d:
            current_time += t
            heapq.heappush(pq, -t)
        elif pq and -pq[0] > t:
            # 堆顶是耗时最长的任务（的负数）
            # 当前任务耗时更短，进行替换
            longest_t = -heapq.heappop(pq)
            current_time -= longest_t
            current_time += t
            heapq.heappush(pq, -t)
            
    print(len(pq))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心算法 + 优先队列（大顶堆）
  • 时间复杂度：，其中 是建筑的数量。排序需要 ，遍历建筑并对优先队列进行操作需要 。
  • 空间复杂度：，用于存储建筑信息和优先队列。