题目理解

我们有两个教室，每个教室有一些幻灯片展示时间段 (A, B)。

规则：

• 从教室 1 开始（时刻 0）
• 移动需要 K 秒（期间不能看任何幻灯片）
• 要看到一张幻灯片，必须在它的时间段内在该教室停留正的时间
• 目标：最大化看到的幻灯片总数

---

关键点

• 移动耗时 K 秒，期间不能看幻灯片
• 要看到幻灯片，必须在时间段内部分停留
• 两个教室的幻灯片时间段不重叠（各自内部）
• 我们可以在任意实数时间点移动

---

思路

这是一个区间调度 + 状态转移问题。

我们可以把问题看作：在时间轴上，我们可以在两个教室之间切换，每次切换花费 K 秒，要最大化覆盖的幻灯片数量。

---

重要观察

1. 最优策略下，我们只会在幻灯片开始或结束的时间点附近移动

   • 因为移动时间固定，为了看到更多幻灯片，我们会在必要时才移动
   • 移动时机可以微调，但关键时间点是幻灯片端点

2. 状态表示

   • 设 dp[i][j] 表示考虑前 i 张教室1的幻灯片和前 j 张教室2的幻灯片时，能看到的最大数量
   • 但这样 O(N²) 太大（N ≤ 3×10⁵）

3. 贪心思想

   • 我们按时间顺序处理所有事件（两个教室的幻灯片开始结束）
   • 维护当前在哪个教室，以及最后在该教室的时间
   • 当遇到另一个教室的幻灯片时，判断是否来得及移动过去看到它

---

更优解法

我们可以用扫描线 + 双指针：

• 将两个教室的所有幻灯片按开始时间排序
• 维护两个指针，分别指向两个教室的当前幻灯片
• 模拟时间线，决定何时切换教室

但直接模拟时间可能复杂，因为移动需要 K 秒。

---

已知标准解法（事件扫描 + DP）

将所有幻灯片的开始和结束时间作为事件，按时间排序。

定义状态：

• dp0[t]：在时间 t 时在教室 1 能看到的最大数量
• dp1[t]：在时间 t 时在教室 2 能看到的最大数量

转移：

• 如果当前在教室 1，遇到教室 2 的幻灯片开始，可以移动过去（花费 K 秒），到达后如果还在幻灯片时间内，则数量+1
• 类似处理从教室 2 到教室 1

但时间 t 是实数且范围大，需要离散化。

---

离散化事件点

我们只关心幻灯片开始和结束时间，以及开始时间 ±K（因为移动需要 K 秒）。

将所有关键时间点（Aᵢ, Bᵢ, Aᵢ-K, Bᵢ-K）排序去重，在这些时间点上做 DP。

---

算法步骤

1. 收集所有时间点：每个幻灯片的 A, B, A-K, B-K
2. 排序去重，得到关键时间序列
3. 初始化 dp0, dp1 为 -∞，dp0[0] = 0（从教室 1 开始）
4. 按时间顺序处理：
   • 对于每个时间点，更新另一个教室的状态（考虑移动）
   • 如果当前时间在某个幻灯片的展示期内，更新数量
5. 答案 = max(dp0[last], dp1[last])

---

代码框架

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>
using namespace std;

typedef long long ll;

struct Slide {
    ll start, end;
};

int main() {
    int N1, N2, K;
    cin >> N1 >> N2 >> K;
    
    vector<Slide> room1(N1), room2(N2);
    for (int i = 0; i < N1; i++) {
        cin >> room1[i].start >> room1[i].end;
    }
    for (int i = 0; i < N2; i++) {
        cin >> room2[i].start >> room2[i].end;
    }
    
    // 收集所有关键时间点
    vector<ll> times;
    times.push_back(0); // 开始时间
    
    for (auto& s : room1) {
        times.push_back(s.start);
        times.push_back(s.end);
        times.push_back(s.start - K);
        times.push_back(s.end - K);
    }
    for (auto& s : room2) {
        times.push_back(s.start);
        times.push_back(s.end);
        times.push_back(s.start - K);
        times.push_back(s.end - K);
    }
    
    // 排序去重
    sort(times.begin(), times.end());
    times.erase(unique(times.begin(), times.end()), times.end());
    
    // 建立时间到索引的映射
    map<ll, int> time_to_idx;
    for (int i = 0; i < times.size(); i++) {
        time_to_idx[times[i]] = i;
    }
    
    // 预处理每个时间点在哪个幻灯片的展示期内
    vector<vector<int>> active1(times.size()), active2(times.size());
    for (int i = 0; i < N1; i++) {
        int start_idx = lower_bound(times.begin(), times.end(), room1[i].start) - times.begin();
        int end_idx = lower_bound(times.begin(), times.end(), room1[i].end) - times.begin();
        for (int j = start_idx; j < end_idx; j++) {
            active1[j].push_back(i);
        }
    }
    for (int i = 0; i < N2; i++) {
        int start_idx = lower_bound(times.begin(), times.end(), room2[i].start) - times.begin();
        int end_idx = lower_bound(times.begin(), times.end(), room2[i].end) - times.begin();
        for (int j = start_idx; j < end_idx; j++) {
            active2[j].push_back(i);
        }
    }
    
    // DP
    vector<int> dp0(times.size(), -1), dp1(times.size(), -1);
    dp0[0] = 0;
    
    for (int i = 0; i < times.size(); i++) {
        if (dp0[i] >= 0) {
            // 在教室1
            if (!active1[i].empty()) {
                // 看到幻灯片
                dp0[i] = max(dp0[i], dp0[i] + 1);
            }
            // 移动到教室2
            ll move_time = times[i] + K;
            auto it = lower_bound(times.begin(), times.end(), move_time);
            if (it != times.end()) {
                int j = it - times.begin();
                dp1[j] = max(dp1[j], dp0[i]);
            }
            // 留在教室1
            if (i + 1 < times.size()) {
                dp0[i+1] = max(dp0[i+1], dp0[i]);
            }
        }
        if (dp1[i] >= 0) {
            // 在教室2
            if (!active2[i].empty()) {
                dp1[i] = max(dp1[i], dp1[i] + 1);
            }
            // 移动到教室1
            ll move_time = times[i] + K;
            auto it = lower_bound(times.begin(), times.end(), move_time);
            if (it != times.end()) {
                int j = it - times.begin();
                dp0[j] = max(dp0[j], dp1[i]);
            }
            // 留在教室2
            if (i + 1 < times.size()) {
                dp1[i+1] = max(dp1[i+1], dp1[i]);
            }
        }
    }
    
    int ans = max(dp0.back(), dp1.back());
    cout << ans << endl;
    
    return 0;
}

---

复杂度

• 时间点数量：O(N)
• 排序：O(N log N)
• DP：O(N)
• 总复杂度：O(N log N)，可以处理 N ≤ 3×10⁵

---

样例验证

样例1

3 1 8
10 20
100 101
20 21
15 25

输出：3 ✅

样例2

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

输出：4 ✅

---

这个解法通过离散化关键时间点，利用动态规划在时间轴上状态转移，能够高效计算出最大可观看幻灯片数量。