P1697 [USACO18JAN] Lifeguards B

题目背景

本题翻译来自 deepseek-v3。

题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

3
5 9
1 4
3 7

输出 #1

7

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;	// 严格要求
ll a[1000100], b[1000100], c[1000100];
int main(){
	ios :: sync_with_stdio(0);	// 提高cin、cout的运行速度
	cin.tie(0);
	cout.tie(0);
	
	ll n, maxn = -1e9;
	cin >> n;
	
	//预处理过程 
	for(ll i = 1; i <= n; i++){
		cin >> b[i] >> c[i];
		for(ll j = b[i]; j < c[i]; j++){
			a[j]++;	
		}
	} 
	
	for(ll i = 1; i <= n; i++){	//当前编号 
		ll sum = 0;
		for(ll j = b[i]; j < c[i]; j++){		//去掉产生的影响 
			a[j]--;	
		}
		//求有效个数
		for(ll j = 0; j <= 1000; j++){
			if(a[j] > 0) sum++;
		} 
		
		//比较有效个数和最小值
		maxn = max(maxn, sum);
		
		for(ll j = b[i]; j < c[i]; j++){		//恢复产生的影响 
			a[j]++;	
		} 
	}
	
	cout << maxn << endl;

    return 0;
}