贪心法是十分常见的算法之一，一般来说写法简单，但是正确性难以证明，比较感性。

🎈 作者：Eriktse
🎈 简介：211计算机在读，CCPC全国赛金牌，ICPC区域赛银牌退役选手🏆力争以通俗易懂的方式讲解编程和算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈欢迎加群一起玩耍~QQ群：600240150

贪心法的使用前提

1.可以找到一个局部最优解。

2.可以从局部最优解，推广到全局最优解。

在课本上，两个条件分别是：最优子结构和贪心选择性质。

一般来说，贪心法往往是将某个东西排序，或者用堆等数据结构，每一步都取局部最优解，进而得到全局最优解。

关于优先队列（堆）的介绍：https://www.eriktse.com/technology/1075.html

分析步骤

1.确定要贪的东西和贪心策略，或者说根据什么东西来贪心。比如某个物品的性价比，我们优先选性价比高的，或者说某个区间，按照左端点还是右端点进行排序等等。

2.从局部的特殊情况出发，简单分析选择“贪心策略”是不劣的，也就是选择贪心的方法，一定不会比其他方法更差。

一般来说，大多数能够贪心的东西，对答案的贡献都相等。比如背包问题中，如果每件物品体积都相等，那肯定是性价比优先。当有多种选择，但是他们对答案的贡献相等时，我们会选择开销较小的，或者是能够给后面留下更多选择空间的。

3.开始贪心，得到问题的解。

例题

ETOJ 1035: 小e看电视

题目链接：http://oj.eriktse.com/problem.php?id=1035

贪心法，当右端点相等的时候，选任意一个合法的区间都一样，且最多选择一个，所以按照右端点升序排列。特殊情况是，区间大小为$0$，为了算上这个区间，可以在右端点相等时按照左端点升序排列。

然后从左到右遍历这个数组，如果合法就选择即可。

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

const int N = 2e5 + 9, T = 20;

struct Node
{
    int l, r;
}a[N];

void solve()
{
    int n;cin >> n;
    for(int i = 1;i <= n; ++ i)cin >> a[i].l >> a[i].r;

    sort(a + 1, a + 1 + n, [](const Node &u, const Node &v)
    {
        return u.r == v.r ? u.l < v.l : u.r < v.r;
    });

    int now = 1, ans = 0;
    for(int i = 1;i <= n; ++ i)
    {
        if(a[i].l < now)continue;
        now = a[i].r, ans ++;
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while(_ --)solve();
    return 0; 
}

ETOJ 1036: 我踏马吃吃吃吃吃

题目链接：http://oj.eriktse.com/problem.php?id=1036

排队取水问题，典型的贪心，我们按照等候时间从小到大排序，然后每次将等候时间最小的人放入“总时间最少的窗口”即可，这个可以用优先队列来维护。

最终计算出的所有人的等待时间之和最小。

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

const int N = 1e6 + 9;

ll a[N];

void solve()
{
    int n, m;cin >> n >> m;
    for(int i = 1;i <= n; ++ i)cin >> a[i];

    sort(a + 1, a + 1 + n);

    priority_queue<ll, vector<ll>, greater<ll>> pq;

    for(int i = 1;i <= m; ++ i)pq.push(0);

    ll ans = 0;
    for(int i = 1;i <= n; ++ i)
    {
        ll x = pq.top();pq.pop();
        pq.push(x + a[i]);
        ans += x;
    }

    cout << ans << '\n';

}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while(_ --)solve();
    return 0; 
}