洛谷每日1题-------Day39__P1697 [USACO18JAN] Lifeguards B

题目背景

本题翻译来自 deepseek-v3。

题目描述

Farmer John 为他的奶牛们开设了一个游泳池，认为这将帮助它们放松并产更多的奶。

为了确保安全，他雇佣了 N 头奶牛作为救生员，每头奶牛的班次覆盖一天中的某个连续时间段。为简单起见，游泳池每天从时间 t=0 开放到时间 t=1000，因此每个班次可以用两个整数描述，分别表示奶牛开始和结束其班次的时间。例如，一头救生员从时间 t=4 开始到时间 t=7 结束，覆盖了 3 个单位的时间（注意端点表示时间点）。

不幸的是，Farmer John 多雇佣了 1 名救生员，超出了他的资金支持范围。鉴于他必须解雇恰好 1 名救生员，剩下的救生员的班次能够覆盖的最长时间是多少？如果至少有一名救生员在场，则某个时间段被视为被覆盖。

输入格式

输入的第一行包含 N（1≤N≤100）。接下来的 N 行每行描述一名救生员，用两个范围在 0…1000 的整数表示该救生员班次的开始和结束时间。所有端点都是唯一的。不同救生员的班次可能会重叠。

输出格式

请输出一个数字，表示如果 Farmer John 解雇 1 名救生员后，剩下的救生员的班次能够覆盖的最长时间。

输入输出样例

输入 #1复制

3
5 9
1 4
3 7

输出 #1复制

7

题解:

#include<iostream>
#include<vector>
using namespace std;// 定义奶牛类，表示每个救生员的班次时间段
class Cow{
public:int t1;  // 班次开始时间int t2;  // 班次结束时间
};int main(){int n, maxTime=0;  // n: 救生员数量, maxTime: 记录最大覆盖时间cin >> n;  // 输入救生员数量vector<Cow> secure;  // 存储所有救生员的班次信息int maxEndTime = 0;  // 记录所有班次的最晚结束时间// 输入每个救生员的班次信息，并更新maxEndTimefor (int i = 0; i < n; i++) {Cow cow;cin >> cow.t1 >> cow.t2;if (cow.t2 > maxEndTime) maxEndTime = cow.t2;  // 更新最晚结束时间secure.push_back(cow);  // 将当前救生员信息存入secure}// 初始化时间轴数组，记录每个时间点被覆盖的次数vector<int> time;time.resize(maxEndTime);  // 时间轴长度为maxEndTime// 遍历所有救生员，统计每个时间点被覆盖的次数for(int i = 0; i < n; i++) {// 将当前救生员的班次时间段内的所有时间点覆盖次数+1for(int j = secure[i].t1; j < secure[i].t2; j++) {++time[j]; }}// 尝试解雇每一个救生员，计算剩余救生员的覆盖时间for(int i = 0; i < n; i++) {vector<int> temp = time;  // 复制时间轴数组int currentCount = 0;     // 记录当前解雇方案下的覆盖时间// 模拟解雇第i个救生员，将其班次时间段内的覆盖次数-1for(int j = secure[i].t1; j < secure[i].t2; j++) {--temp[j];}// 统计剩余救生员覆盖的总时间（temp[k] > 0 表示该时间点被覆盖）for(int k = 0; k < time.size(); k++) {if(temp[k] > 0) currentCount++;}// 更新最大覆盖时间if(currentCount > maxTime) maxTime = currentCount;}cout << maxTime << endl;  // 输出结果return 0;
}