C++ 贪心算法 学习笔记

做题又遇到贪心了，这次我一定要攻下来。

什么是贪心算法？

贪心算法 / 贪婪算法（greedy algorithm），是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

换句话说，我只考虑这个阶段的最佳选择，而不是直接从全局入手综合考虑。当我每一步都都是最佳选择的时候，那么最后一步做完了，应该也就是最佳的选择了。

贪心算法不是所有问题都能得到最优解，关键是选择正确的贪心策略。

贪心算法一般按如下步骤进行：

1. 建立数学模型来描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每个子问题求解，得到子问题的局部最优解。

4. 把子问题的解局部最优解合成原来解问题的一个解。

什么时候用贪心算法？

贪心策略的前提是：局部最优策略能产生全局最优解。

实际上，贪心算法使用的情况比较少，一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析可以做出判断。

例题

答疑

题目分析
要使发消息时刻之和最小，需合理安排答疑顺序。通过贪心策略，按每位同学的（进入时间 + 答疑时间 + 离开时间）总和由小到大排序。该策略可保证后续同学尽早开始答疑，降低总时间累积。

实现代码

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

struct Student {
    int s, a, e;
    int total() const { return s + a + e; }
};

int main() {
    int n;
    cin >> n;
    vector<Student> students(n);
    for (int i = 0; i < n; ++i)
        cin >> students[i].s >> students[i].a >> students[i].e;
    
    sort(students.begin(), students.end(), [](const Student& x, const Student& y) {
        return x.total() < y.total();
    });
    
    long long current_time = 0, sum = 0;
    for (const auto& stu : students) {
        sum += current_time + stu.s + stu.a;
        current_time += stu.s + stu.a + stu.e;
    }
    cout << sum;
    return 0;
}

算法说明

1. 结构体封装：整合学生的时间参数（进入/答疑/离开）
2. 排序规则：按总处理时间（s+a+e）升序排列
3. 时间计算：
   • 发消息时刻 = 当前队列总耗时 + 当前学生进入和答疑时间
   • 总耗时更新时需包含完整处理时间（含离开时间）

复杂度

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)