题解

本题使用排序 + 贪心 + 前缀和求解艺术展览的最大闲暇时间问题。

算法思路：

1. 问题理解：

   • 有 $n$ 个展览，每个展览有开始时间 $a[i].first$ 和持续时间 $a[i].second$
   • 需要按顺序参观展览（可以跳过某些展览）
   • 目标：最大化总闲暇时间（等待时间）

2. 预处理：

   • 按开始时间对展览排序
   • 计算展览持续时间的前缀和：$a[i].second = \sum_{j=1}^{i} duration[j]$
   • 这样 $a[i].second$ 表示参观完前 $i$ 个展览需要的总时间

3. 贪心策略：

   • 维护 mxl：表示到目前为止的最大"空闲"值
   • 对于每个展览 $i$，计算：
     • $mxl = \max(mxl, a[i].first - a[i-1].second)$
     • 这表示第 $i$ 个展览开始时间减去之前所有展览的总时间
   • 答案更新：$ans = \max(ans, mxl + a[i].second - a[i].first)$

4. 公式理解：

   • $a[i].first - a[i-1].second$：第 $i$ 个展览开始前的空闲时间
   • $mxl + a[i].second - a[i].first$：选择前面的某个子序列和当前展览的总闲暇时间
   • 核心思想：前面选择的展览尽可能早结束，留出更多空闲时间

5. 动态更新：

   • 遍历每个展览，动态更新最大空闲值
   • 每次考虑是否将当前展览加入序列

时间复杂度：$O(n \log n)$，主要是排序的时间复杂度。

这是一道巧妙的贪心问题，关键在于理解如何最大化闲暇时间。

#include <iostream>
#include <algorithm>

using namespace std;
using LL = long long;
using Pii = pair<LL, LL>; 

const int N = 5e5 + 5; 

int n;
Pii a[N];

int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].first >> a[i].second;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) {
    a[i].second += a[i - 1].second;
  }
  LL mxl = 0, ans = 0; 
  for (int i = 1; i <= n; ++i) {
    mxl = max(mxl, a[i].first - a[i - 1].second);
    ans = max(ans, mxl + a[i].second - a[i].first);
  }
  cout << ans << '\n';
  return 0; 
}