题目大意

Bajtazar 需要剪辑 $n$ 部视频，第 $i$ 部视频需要 $t_i$ 天完成，并且必须在第 $d_i$ 天之前发布。他只有一台电脑，一次只能剪辑一部视频。求最多能按时发布多少部视频，并给出一个具体的工作计划。

算法分析

这是一个经典的带期限的作业调度问题，可以使用贪心算法结合优先队列来解决。

核心思路

1. 排序策略：将所有视频按照截止时间 $d_i$ 从小到大排序
2. 贪心选择：依次考虑每个视频，维护当前已选择视频的总耗时
3. 反悔机制：当无法加入当前视频时，如果它比已选视频中耗时最长的更短，就进行替换

算法步骤

1. 输入处理：读取 $n$ 和所有 $(t_i, d_i)$ 对
2. 排序：按 $d_i$ 升序排序
3. 贪心选择：
   • 使用大根堆维护已选视频的耗时
   • 遍历排序后的视频：
     • 如果当前总时间 $sum + t_i \leq d_i$，直接选择该视频
     • 否则，如果堆顶元素（最大耗时）大于 $t_i$，则替换
4. 输出：输出选择的视频数量和具体调度方案

正确性证明

该算法的正确性基于以下观察：

• 最优解中，选择的视频应该按照期限顺序完成
• 当无法加入新视频时，替换掉耗时最长的视频可以给后续视频留出更多时间
• 这种反悔贪心策略可以保证选择尽可能多的视频

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 500005;

struct Video {
    int id, t, d;
    bool operator<(const Video& other) const {
        return d < other.d;
    }
};

Video videos[MAXN];
int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> videos[i].t >> videos[i].d;
        videos[i].id = i + 1;
    }
    
    // 按截止时间排序
    sort(videos, videos + n);
    
    // 大根堆，存储(t, id)
    priority_queue<pair<int, int>> pq;
    ll current_time = 0;
    
    // 第一遍：确定选择哪些视频
    for (int i = 0; i < n; i++) {
        int t = videos[i].t, d = videos[i].d, id = videos[i].id;
        
        if (current_time + t <= d) {
            // 可以直接加入
            current_time += t;
            pq.push({t, id});
        } else if (!pq.empty() && pq.top().first > t) {
            // 替换掉耗时更长的视频
            current_time = current_time - pq.top().first + t;
            pq.pop();
            pq.push({t, id});
        }
    }
    
    // 输出结果
    int m = pq.size();
    cout << m << "\n";
    
    if (m == 0) {
        return 0;
    }
    
    // 提取选择的视频
    vector<pair<int, int>> selected;
    while (!pq.empty()) {
        selected.push_back({pq.top().second, pq.top().first});
        pq.pop();
    }
    
    // 按原顺序重新排序选择的视频
    vector<Video> final_selected;
    for (auto& p : selected) {
        int id = p.first;
        for (int i = 0; i < n; i++) {
            if (videos[i].id == id) {
                final_selected.push_back(videos[i]);
                break;
            }
        }
    }
    
    // 按截止时间排序并输出调度方案
    sort(final_selected.begin(), final_selected.end());
    
    ll start_time = 1;
    for (auto& video : final_selected) {
        cout << video.id << " " << start_time << "\n";
        start_time += video.t;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 排序：$O(n \log n)$
  • 堆操作：每个元素最多入堆出堆一次，$O(n \log n)$
• 空间复杂度：$O(n)$，用于存储视频信息和堆

样例解释

样例1

输入：

5
4 5
2 4
5 3
1 9
3 10

处理过程：

1. 排序后：$(5,3), (2,4), (4,5), (1,9), (3,10)$
2. 选择视频：ID 2($t=2$), ID 4($t=1$), ID 5($t=3$)
3. 调度：第2个视频第3天开始，第4个视频第7天开始，第5个视频第8天开始

输出：

3
2 3
4 7
5 8

总结

本题的关键在于理解期限调度问题的贪心策略，以及如何通过反悔机制来优化选择。使用优先队列可以高效地维护当前选择集合，确保在 $O(n \log n)$ 时间内解决问题。

这种"排序 + 堆"的贪心模式在很多调度问题中都有应用，掌握这种思路对解决类似问题很有帮助。