百度之星2015：1001题贪心算法的ACMer解法与优化

问题背景与贪心算法的适配性

2015年百度之星编程竞赛1001题（以下简称“1001题”）是一道典型的资源分配问题，题目要求在给定一组任务（每个任务包含执行时间、优先级、截止时间等属性）和总可用资源的情况下，通过调度算法最大化任务完成数量或总优先级。此类问题天然适配贪心算法，因其核心在于通过局部最优选择（如优先执行短任务、高优先级任务或截止时间早的任务）逼近全局最优解。

贪心算法的适配性体现在两方面：

1. 问题可分解性：任务调度可拆分为独立的选择步骤，每一步的选择仅依赖当前状态（如剩余资源、未执行任务列表）；
2. 最优子结构：局部最优选择（如优先执行耗时最短的任务）能直接贡献于全局目标（最大化完成数量）。

例如，若目标为“在限定时间内完成最多任务”，则贪心策略应优先选择执行时间最短的任务（Shortest Job First, SJF），其正确性可通过反证法证明：若存在更优解未选择最短任务，则替换为最短任务后总完成数不变或增加，与假设矛盾。

贪心策略的设计与实现

1. 关键贪心规则的选择

1001题的核心在于选择合适的贪心规则。常见规则包括：

• 按执行时间升序排序（SJF）：适用于“完成最多任务”目标；
• 按优先级降序排序：适用于“总优先级最大化”目标；
• 按截止时间升序排序（Earliest Deadline First, EDF）：适用于“避免任务超时”目标。

实际解题中需结合题目具体约束。例如，若题目要求“在总时间T内完成尽可能多的高优先级任务”，则需设计复合规则：

1. 按优先级降序排序；
2. 同优先级任务按执行时间升序排序。

2. 算法实现步骤

以“完成最多任务”为目标，算法流程如下：

1. 输入处理：读取任务列表，提取每个任务的执行时间time_i；
2. 排序：按time_i升序排序；
3. 贪心选择：遍历排序后的任务列表，依次选择任务，若当前剩余时间remaining_time >= time_i，则执行并减少剩余时间；
4. 输出结果：统计完成的任务数量。

示例代码（C++）：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Task {
    int id;
    int time;
};
bool compareByTime(const Task &a, const Task &b) {
    return a.time < b.time;
}
int maxTasks(int T, vector<Task>& tasks) {
    sort(tasks.begin(), tasks.end(), compareByTime);
    int count = 0;
    int remaining = T;
    for (const auto &task : tasks) {
        if (remaining >= task.time) {
            remaining -= task.time;
            count++;
        }
    }
    return count;
}
int main() {
    int T = 10; // 总可用时间
    vector<Task> tasks = {{1, 3}, {2, 2}, {3, 5}, {4, 1}};
    cout << "Max tasks: " << maxTasks(T, tasks) << endl;
    return 0;
}

边界条件与反例处理

贪心算法的局限性在于其局部最优性可能导致全局非最优解。例如，若题目要求“总优先级最大化”且任务执行时间与优先级负相关（即短任务优先级低），则单纯按执行时间排序会忽略高优先级长任务。此时需调整贪心规则：

1. 复合排序：按优先级降序、执行时间升序排序；
2. 动态规划辅助：在贪心选择前预处理任务，排除明显非优解（如超时任务）。

反例验证：
假设任务列表为[(time=2, priority=1), (time=3, priority=2)]，总时间T=3。

• 若按执行时间排序，选择第一个任务（完成数1，优先级1）；
• 若按优先级排序，选择第二个任务（完成数1，优先级2）。
  显然，后者更优，因此需优先按优先级排序。

性能优化与复杂度分析

贪心算法的时间复杂度主要由排序步骤决定。对于n个任务，排序复杂度为O(n log n)，遍历复杂度为O(n)，总复杂度为O(n log n)。

优化方向：

1. 快速选择：若仅需前k个最优任务，可使用快速选择算法将复杂度降至O(n)；
2. 并行排序：对大规模任务列表，可采用并行排序算法（如GPU加速）；
3. 增量更新：若任务列表动态变化（如在线调度），可使用堆结构维护最优任务。

示例：使用优先队列（堆）实现动态调度：

#include <queue>
struct Task {
    int priority;
    int time;
};
struct Compare {
    bool operator()(const Task &a, const Task &b) {
        return a.priority < b.priority; // 大顶堆
    }
};
int maxPriorityTasks(int T, vector<Task>& tasks) {
    priority_queue<Task, vector<Task>, Compare> pq;
    for (auto &task : tasks) pq.push(task);
    int totalPriority = 0;
    while (!pq.empty() && T > 0) {
        auto task = pq.top(); pq.pop();
        int execute = min(task.time, T);
        totalPriority += task.priority * execute; // 假设优先级按时间累积
        T -= execute;
    }
    return totalPriority;
}

实际应用中的扩展思考

1. 多维度贪心：实际场景中任务可能包含多个属性（如资源消耗、依赖关系），需设计多维度贪心规则。例如，云计算资源分配中需同时考虑CPU、内存和I/O；
2. 混合策略：结合贪心与动态规划，如先用贪心缩小解空间，再用动态规划求解剩余问题；
3. 近似算法：对NP难问题，贪心算法可作为近似算法，通过理论证明其近似比（如调度问题的2-近似）。

例如，某云厂商的虚拟机调度系统可能采用贪心策略优先分配短任务，同时结合动态规划处理长任务依赖，以平衡响应速度与资源利用率。

总结与ACMer建议

1001题的贪心解法核心在于问题建模与贪心规则的选择。ACMer需注意：

1. 明确目标函数：是最大化完成数、总优先级还是其他指标；
2. 验证贪心正确性：通过反例或数学证明确保局部最优能导致全局最优；
3. 处理边界条件：如任务执行时间超过总时间、优先级相同等情况。

实际编程竞赛中，建议先实现基础贪心解法，再通过优化数据结构（如堆、并查集）提升性能。对于复杂场景，可参考行业常见技术方案中的混合策略设计。