A27371. 战胜白蚁
填空题
较易
知识点
题目描述
战胜白蚁
题目描述
小明因为很长时间没有回家，发现他家被白蚁给入侵了，白蚁特别喜欢啃食木头，因此他家的地板就遭殃了。小明要抢救被白蚁破坏的木地板，每个木地板由于白蚁的数量不同，每个地板进行维修的时间也不同，同时要争取及时修理越好，否则超过某个时间，这块地板就会被严重破坏掉。小明只能一块一块的清理白蚁，不能并行操作，也就是不能同时修多块地板。
请编写一个程序，根据每个地板的修理时间和如果不修理就会被白蚁完全损毁的时间，进行一个最合理的排序，使得可以抢救最多的木板。输入是木板的数目，以及每个木板的维修时间和被破坏的时间，输出是能抢救的最多木板的数量。
输入格式
第一行是一个整数 N（N 小于 50000），接下来 N 行每行两个整数 T1,T2描述一个要修理的木板：修理这个木板需要 T1秒，如果在 T2秒之内还没有修理完成，这个木板就报废了。
输出格式
输出一个整数 S，表示最多可以抢修 S 个木板。
样例输入
4
100 200
200 1300
1000 1250
2000 3200样例输出
3注意事项
请严格按要求输出，不要多余的打印语句，例如：“输入 x=...” 等多余内容。本程序的代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main 函数需要返回 0。
注意: 只使用 ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include<xxx>， 不能通过工程设置而省略常用头文件。
参考答案
#include <bits/stdc++.h>
using namespace std;
// 定义结构体 Board，用于存储每个木板的维修时间和破坏时间
struct Board {
int repairTime; // 维修一块木板所需的时间
int destroyTime; // 若未在该时间内维修好，木板会损坏的时间
};
// 比较函数，用于对木板按照破坏时间减去维修时间的差值进行比较
bool compare(Board a, Board b) {
return a.destroyTime - a.repairTime < b.destroyTime - b.repairTime;
}
// 救援木板的函数，输入木板数量 N
int rescueBoards(int N) {
Board boards[N]; // 创建一个大小为 N 的 Board 类型数组，用于存储木板信息
// 循环读取每块木板的维修时间和破坏时间
for (int i = 0; i < N; i++) {
cin >> boards[i].repairTime >> boards[i].destroyTime;
}
// 对木板数组按照比较函数进行排序
sort(boards, boards + N, compare);
int time = 0; // 记录已花费的维修总时间
int count = 0; // 记录成功抢救的木板数量
// 遍历排序后的木板数组
for (int i = 0; i < N; i++) {
time += boards[i].repairTime; // 累加当前木板的维修时间
// 如果累加后的维修总时间小于等于当前木板的破坏时间
if (time <= boards[i].destroyTime) {
count++; // 抢救成功数量加 1
} else { // 否则，无法在规定时间内维修这块木板
break; // 停止后续计算
}
}
return count; // 返回抢救成功的木板数量
}
// 主函数
int main() {
int N; // 存储输入的木板数量
cin >> N; // 读取木板数量
int result = rescueBoards(N); // 调用救援木板函数并获取结果
cout << result << endl; // 输出抢救成功的木板数量
return 0;
}
上一题
下一题