【题目来源】
洛谷：[P4053 JSOI2007] 建筑抢修 - 洛谷
【题目描述】
小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有 \(N\) 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
【输入】
第一行，一个整数 \(N\)。
接下来 \(N\) 行，每行两个整数 \(T_1,T_2\) 描述一个建筑：修理这个建筑需要 \(T_1\) 秒，如果在 \(T_2\) 秒之内还没有修理完成，这个建筑就报废了。
【输出】
输出一个整数 \(S\)，表示最多可以抢修 \(S\) 个建筑。
【输入样例】
4
100 200
200 1300
1000 1250
2000 3200
【输出样例】
3
【算法标签】
《洛谷 P4053 建筑抢修》 #贪心# #优先队列# #各省省选# #江苏# #2007#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型
const int MAX_N = 150005; // 定义最大任务数
int n; // 任务数量
int sum = 0; // 当前累计修理时间
int ans = 0; // 最多能完成的任务数// 任务结构体，包含修理时间和截止时间
struct Node
{int a; // 修理所需时间int b; // 截止时间// 重载小于运算符，按截止时间排序bool operator < (Node &x) {return b < x.b;}
} t[MAX_N]; // 任务数组priority_queue<int> q; // 大根堆，维护已选任务的修理时间signed main()
{// 输入任务数量cin >> n;// 输入每个任务的修理时间和截止时间for (int i = 1; i <= n; i++)cin >> t[i].a >> t[i].b;// 按截止时间升序排序sort(t + 1, t + n + 1);// 遍历所有任务for (int i = 1; i <= n; i++){sum += t[i].a; // 累计修理时间q.push(t[i].a); // 将当前任务加入堆// 如果当前累计时间不超过截止时间if (sum <= t[i].b)ans++; // 可以完成该任务else{// 否则移除修理时间最长的任务sum -= q.top();q.pop();}}// 输出最多能完成的任务数cout << ans << endl;return 0;
}
【运行结果】
4
100 200
200 1300
1000 1250
2000 3200
3