洛谷P4188 [USACO18JAN] Lifeguards S 题解

题目链接：P4188 [USACO18JAN] Lifeguards S

题意：

FJ 为他的奶牛们建造了一个游泳池，FJ 认为这将有助于他们放松身心以及生产更多牛奶。

为了确保奶牛们的安全，FJ 雇佣了 $N$ 头牛，作为泳池的救生员，每一个救生员在一天内都会有一定的事情，并且这些事情都会覆盖一天内的一段时间。为了简单起见，泳池从时间 $t=0$ 时开门，直到时间 $t=10^9$ 关门，所以每个事情都可以用两个整数来描述，给出奶牛救生员开始以及结束事情的时间。例如，一个救生员在时间 $t=4$ 时开始事情并且在时间 $t=7$ 时结束事情，那么这件事情就覆盖了 $3$ 个单位时间。（注意：结束时间是“点”的时间）

不幸的是，FJ 多雇佣了一名的救生员，但他没有足够的资金来雇佣这些救生员。因此他必须解雇一名救生员，求可以覆盖剩余救生员的轮班时间的最大总量是多少？如果当时至少有一名救生员的事情已经开始，则这个时段被覆盖。

输入格式：

输入的第一行包括一个整数 $N\ ( 1 \le N \le 100000)$。接下来 $N$ 行中，每行告诉了我们一个救生员在 $0 \sim 10^9$ 范围内的开始以及结束时间。所有的结束时间都是不同的。不同的救生员的事情覆盖的时间可能会重叠。

输出格式：

输出一行一个整数，如果 FJ 解雇一名救生员仍能覆盖的最大时间。

不知道为啥dp不对啊（虽然看着也不对

题解的做法看上去挺简洁的。先把覆盖的总时间算出来，再减掉贡献最小的那个。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,mx,mn=INF,res; struct node { int l,r; } a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
    sort(a + 1, a + 1 + n, [](node a, node b) { return a.l < b.l; });
    
    for(int i = 1; i <= n; i++) if(a[i].r > mx) {
        res += a[i].r - max(mx, a[i].l); mx = a[i].r;
    }
    mx = 0; a[n + 1].l = a[n].r;
    for(int i = 1; i <= n; i++) {
        if(a[i].r <= mx) mn = 0; else {
            down(mn, min(a[i + 1].l, a[i].r) - max(a[i].l, mx)); up(mx, a[i].r);
        }
    }
    cout << res - max(0ll, mn) << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/sinmys/solution-p4188