贪心算法（蓝桥杯 C++ 题目 代表 注解）

介绍：

贪心���法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望最终能够得到全局最好或最优的结果的算法。它通常用来解决一些最优化问题，如最小生成树、最短路径等。

贪心算法的核心思想是每次都选择局部最优解，而不考虑全局的情况。通过不断地做出局部最优选择，整体上就能得到一个接近最优解的解。

然而，贪心算法并不是在所有情况下都能得到最优解。由于贪心算法只考虑当前的最优选择，而不进行回溯，可能会导致最终结果并非全局最优解。因此，在使用贪心算法时，需要确保问题具备贪心选择性质（即局部最优解能够导致全局最优解）以及最优子结构性质（即问题的最优解包含了其子问题的最优解）。

在应用贪心算法时，可以采用贪心选择、最优子结构和证明最优性三个步骤来设计算法。首先，通过贪心选择找到局部最优解；然后，通过证明最优性来证明贪心选择是安全的；最后，通过最优子结构来将问题分解为子问题，并迭代地求解子问题。

总之，贪心算法是一种简单而有效的算法，可以在一些满足贪心选择性质和最优子结构性质的问题上得到最优解。然而，在应用贪心算法时需要注意验证问题的性质，以确保得到正确的结果。

题目一（找零问题）：

 ​​

代码： 

#includeusing namespace std;int main(){    int n, i = 1;    cin >> n;    int a[6] = { 0,100,50,20,5,1 };    int cnt[6] = { 0 };        while (n)        {            cnt[i] = n / a[i];            n -= cnt[i] * a[i];            i++;        }    for (int i = 1; i  x;for (int i = 0; i  student[i].s >> student[i].a >> student[i].e;        student[i].sum = student[i].s + student[i].a + student[i].e;    }    sort(student + 1, student + n + 1, cmp);//排序，从小到大    long long time = student[1].s + student[1].a;//第一个学生此时发    long long ans = time;    for (int i = 2; i