题解P4188【[USACO18JAN]Lifeguards S】

· · 题解

洛谷传送门

思路

先回顾一下如何求所有区间的覆盖长度。

可以先将所有区间按照左边界排序，然后按顺序处理每个区间。

同时维护已覆盖的右边界。每次对当前区间新增的长度进行累加，并更新右边界。

现在要删掉一个区间。

如果枚举每个要删掉的区间，再重新计算覆盖长度，效率太低。

我们应该考虑删掉一个区间后，覆盖总长的变化，即只被删掉的区间覆盖的长度。

由于⼀个区间可能包含多个区间。

这样就导致了只被该区间覆盖的区域是多个不连续的段，统计总⻓较为麻烦。

但仔细思考，我们的目标是求出最小单独覆盖长度。

如果出现这种情况，我们必然可以选取被包含的区间。

它的单独覆盖长度为 0 ，从而直接得到最优答案。

此外，如果⼀个区间相邻的两个区间由交集。

那么它也是会被完全覆盖的，可以删除且覆盖总⻓不减。

我们对所有区间进行一遍扫描，就能检查出上述两种情况。

如果上述两种情况都不存在，说明一个区间最多只会跟相邻两个区间有交。

那么它的单独覆盖⻓度就可以直接计算出来了。

⽤⾃身的覆盖⻓度减去与相邻区间交的⻓度即可。

复杂度分析

时间复杂度

排序 O(N \log N) 。

求覆盖总⻓ O(N) 。

求每个区间单独覆盖长度 O(N) 。

总时间复杂度为 O(N \log N) 。

空间复杂度

记录区间 O(N) 。

code

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int kMaxN = 1e5 + 2;

struct E {
  int l, r;
  bool operator<(const E &e) const {  // 按照左边界排序
    return l < e.l;
  }
} e[kMaxN];
int n, t;

int F() {                                                    // 计算一只奶牛独占的最短时间
  int v = 1e9;                                               // 初始化最值
  e[0].r = e[1].l, e[n + 1] = {e[n].r, 1 << 30};             // 构造左右边界区间
  for (int i = 1; i <= n; i++) {                             // 逐个处理区间
    if (e[i].r <= e[i - 1].r || e[i + 1].l <= e[i - 1].r) {  // 被上个区间包含，或相邻区间接上了
      return 0;
    }
    v = min(v, min(e[i + 1].l, e[i].r) - e[i - 1].r);  // 去除当前区间重叠的部分
  }
  return v;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> e[i].l >> e[i].r;
  }

  sort(e + 1, e + 1 + n);

  for (int i = 1, r = e[1].l; i <= n; i++) {  // 逐个区间累加新增长度
    t += max(e[i].r - max(e[i].l, r), 0);     // 从已覆盖右边界开始计算新长度
    r = max(r, e[i].r);                       // 更新已覆盖右边界
  }
  cout << t - F();
  return 0;
}