事实上，贪心并不属于一种特定的算法，而是一种极为重要的算法思想。
基础的大家都会，主要讲一下三种常见的贪心证明方式，即：
-
前面忘了
-
邻项交换法
-
数学归纳法
然后就是，贪心和 dp 都仅适用于具有最优子结构（局部最优解能推导出全局最优解）的问题。唯一不同的一点是，dp 是将所有子问题的最优解全部求出（不考虑优化的前提下），而贪心则状态量要少得多，这也是为什么贪心的时间复杂度往往优于 dp。
接下来进入例题。
线段覆盖问题
按右端点排序即可模拟贪心。
总结：「将更宝贵的地方腾出来」或者说「让前面的 / 后面的选择面更广」是贪心的常见策略。
P2672
经典题。
我们考虑按照疲劳值从大到小排序，进行贪心。
我们首先考虑选上前 \(X\) 个人，他们的贡献用前缀和统计一下即可。
这时，是否可以舍弃一点疲劳值，换取距离上的更优呢？答案显然是肯定的，我们可以考虑置换一个人出去，换取后面一个人加入队伍。考虑到置换不一定更优，所以需要和第一部分取个 \(\max\)。这部分处理一个后缀 \(\max\) 即可。
那么，是否还有可能置换出更多的人？不可能。以置换两个人为例，当置换完第一个人之后，新加进来的人一定是后面贡献最大的，之后置换的那个人，不仅贡献没他多，疲劳值也没有我自己大，那肯定不置换更优。更多的人同理。
最后一个问题，为什么不按照距离从大到小排序？感性理解一下，我舍弃疲劳值换取距离可以获得两倍（因为有来回），但舍弃距离换取疲劳值只有一倍，而且后者能得到的最优方案前者同样找得到，这表明前者一定不劣于后者，于是按照疲劳值从大到小排序。
实现
#include<bits/stdc++.h>
using namespace std;const int N=1e5+5;
int n;
int sum[N],suf[N];
struct NODE{int dis,a;
}b[N];bool cmp(NODE &x,NODE &y){return x.a>y.a;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>b[i].dis;for(int i=1;i<=n;i++)cin>>b[i].a;sort(b+1,b+n+1,cmp);for(int i=n;i>=1;i--)suf[i]=max(suf[i+1],b[i].a+2*b[i].dis);int dismax=-1e9;for(int i=1;i<=n;i++){sum[i]=sum[i-1]+b[i].a;dismax=max(dismax,2*b[i].dis);cout<<max(sum[i]+dismax,sum[i-1]+suf[i])<<'\n';}return 0;
}
总结：排序、置换技巧。
CF865D
反悔贪心入门。
每一天，能对我产生影响的操作只有两个：买和卖。这促使我们考虑反悔贪心。
对于第 \(i\) 天，我首先卖前面买价最低的那一只股票（维护一个大根堆即可）。但有可能这次操作并不是最优的，所以我考虑把它的卖价扔到堆中竞争最低价。
为什么这样是对的呢？考虑第 \(i\) 天的利润，即 \(p_i-\min\)，如果我在第 \(j\) 天以 \(p_i\) 为 \(\min\) 卖出了 \(p_j\) 的股票，则利润为 \(p_j-p_i\)，两者相加，得到 \(p_j-\min\)，这便相当于我在第 \(j\) 天作出了「反悔」的决策。
实现（十分 naive）
#include<bits/stdc++.h>
#define int long long
using namespace std;const int N=3e5+5;
int n,p[N];
priority_queue<int,vector<int>,greater<int> > pq;signed main(){cin>>n;int ans=0;for(int i=1;i<=n;i++){cin>>p[i],pq.push(p[i]);if(p[i]>pq.top()){ans+=p[i]-pq.top();pq.pop(),pq.push(p[i]);}} cout<<ans;return 0;
}
总结：反悔贪心通常直接作出决策，然后维护一些堆来进行「反悔」。