有些题 dp 是难做的或做不了的，这个时候可以去设计一种策略使得决策尽可能最优，也就是贪心。可以说贪心有时候是一种乱搞，但乱搞也能搞出出题人想不到的正解。
反悔贪心
有些题中直接 dp 的复杂度很高并且很难优化或者有后效性无法 dp，朴素贪心考虑可以做到 \(O(n)\) 但是无法保证正确性，这个时候可以使用反悔贪心，在一般是 \(O(n\log n)\) 的时间内完成问题的求解。
相对于普通贪心而言，反悔贪心特殊的点在于“反悔”操作。普通贪心在完成某个阶段的求解后就不会再管那个阶段的决策是否最优，求的是局部最优解而不一定是全局最优解，但反悔贪心可以改变之前的决策，即“反悔”操作。按照判断方式的不同，反悔贪心可以分为反悔堆和反悔自动机两种方法，一般都用到了优先队列实现。
大概流程：先按普通贪心的思路做，用一个优先队列记录每个决策点的决策，当判断出不优的情况就从优先队列中取出最大/小的元素，也就是对之前的决策进行反悔操作，并更新答案。反悔贪心有一些模型，并且贪心题都还是重在思维的锻炼和积累，多做点题吧，还能学 OI 的日子不多了。
P2107 小Z的AK计划
价值一定模型。但这个题比较简单。
首先很明显，我们一定是按 \(x_i\) 从小到大来选点，回头一定不优，所以先把所有点按 \(x\) 排序。贪心过程中每次加入点时先累加上所需时间，把这个点塞入大根堆中，如果累计花费时间 \(>m\) 那么就将堆顶元素，也就是耗时最大的点取出，总时间减去 \(t_i\)，但注意不要减去 \(x_i-x_{i-1}\)，因为路过的时间是必须要算的。还有注意每次取完点后答案都要取最大值。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<ll,ll>
#define fi first
#define se second
const ll N=114514,M=1919810,inf=1e18;
ll n,m,ans,res;
priority_queue <ll> q;
struct xx{
ll x,t;
}a[N];
bool cmp(xx x,xx y){
return x.x<y.x;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].t;
sort(a+1,a+n+1,cmp);
ll sum=0;
for(int i=1;i<=n;++i){
if(a[i].x>m) break;
sum+=a[i].t+a[i].x-a[i-1].x,++res;
q.push(a[i].t);
if(sum>m){
sum-=q.top(),--res;
q.pop();
}
ans=max(ans,res);
}
cout<<ans;
return 0;
}//好像也没多难？