原理与步骤

问题分析​
在有限的时间内安排任务，每个任务有截止时间和得分，需选择任务使得总得分最大。核心思路是贪心算法：优先处理高得分任务，并尽可能将其安排在截止时间的最晚时间点，避免影响其他任务。

关键观察​

• 贪心策略：按得分降序排序任务，优先处理高得分任务。
• 时间分配优化：对每个任务，从截止时间的最晚点向前寻找空闲时间，最大化后续任务的安排空间。

步骤​

1. ​输入处理：读取任务数量 n，以及每个任务的截止时间和得分。
2. ​任务排序：按得分从高到低排序所有任务。
3. ​时间分配：
   • 初始化数组 b 记录时间点是否被占用。
   • 遍历每个任务，从截止时间的最晚点（d-1）向前找到第一个空闲时间点。
   • 若找到，标记该时间点并累加得分。
4. ​输出结果：输出总得分的最大值。

图示法示例（以 n=3 为例）

1. ​排序后顺序：A → B → C。
2. ​分配过程：
   • ​任务A：检查时间1，标记为占用，总得分100。
   • ​任务B：检查时间1（已占用），找到时间0，标记，总得分180。
   • ​任务C：检查时间0（已占用），无法安排。
3. ​最终总得分：180。

代码程序与注释

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

// 自定义比较函数：按得分降序排列
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second; // 高得分优先
}

int main() {
    int n, m = 0;
    cin >> n;
    vector<pair<int, int>> game(n); // 存储任务（截止时间，得分）
    vector<int> b(n, 0); // 记录时间点是否被占用

    // 输入截止时间和得分
    for (int i = 0; i < n; i++) cin >> game[i].first;
    for (int i = 0; i < n; i++) cin >> game[i].second;

    sort(game.begin(), game.end(), cmp); // 按得分降序排序

    // 遍历所有任务，优先处理高得分任务
    for (int i = 0; i < n; i++) {
        int d = game[i].first; // 当前任务的截止时间
        bool found = false;
        // 从截止时间的最晚点（d-1）向前找空闲时间
        for (int j = d - 1; j >= 0; j--) {
            if (b[j] == 0) {
                b[j] = 1; // 标记时间点为占用
                m += game[i].second; // 累加得分
                found = true;
                break;
            }
        }
        // 若未找到可用时间，跳过该任务
    }

    cout << m << endl;
    return 0;
}

关键代码注释

1. ​排序函数​

   bool cmp(...) { return a.second > b.second; }

   按得分降序排列，确保优先处理高收益任务。

2. ​时间分配逻辑​

   for (int j = d - 1; j >= 0; j--) { ... }

   从截止时间的最晚点向前遍历，找到第一个可用时间点。

3. ​得分累加​

   m += game[i].second;

   成功分配时间后，将当前任务的得分加入总分。

时间复杂度

• ​时间复杂度：O(n²)
  排序时间复杂度为 O(n log n)，但任务分配的双层循环最坏需 O(n²)（例如所有任务截止时间相同）。
• ​空间复杂度：O(n)
  使用数组 b 和 game 存储任务和时间状态。

总结

• ​正确性：贪心策略正确，代码能正确处理所有合法输入（假设截止时间 d ≤ n）。
• ​效率问题：在 n 较大时（如 n=1e4），O(n²) 复杂度可能超时，需优化。
• ​改进方向：
  • 使用并查集（Disjoint Set Union, DSU）优化时间点查找，将内层循环降至均摊 O(α(n))，总复杂度 O(n log n)。
  • 例如，维护每个时间点的下一个可用位置，快速跳过已占用区间。