顾名思义，就是对之前的一些决策进行反悔的贪心。
比如你去爬山，你爬到比之前都高的一个点，你就可以认为这是最高的山，
再往上爬，爬到了一个更高点，你就可以撤回一条消息反悔，认为这个点才是最高点。
接下来看几道例题，理解一下
例题
例题 1
P2949 [USACO09OPEN] Work Scheduling G
显然的贪心，将每个工作的截止时间从小到大排序，优先做那些急的事情。
可能有一些事虽然急，但无关紧要，有的不急，但是能收获更多，所以要用堆来维护已经选择的工作收获，收获小的放在前面，遇到收获更大的就替换掉。
Accepted Code
/*Code By Manipula*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct Work{
int s, v;
}a[N];
int n, ans, sum, tot;
bool cmp(Work aa, Work bb){return aa.s < bb.s;}
priority_queue<int, vector<int>, greater<int> > q;
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i].s >> a[i].v;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
sum += a[i].v; q.push(a[i].v); tot++;
if (tot > a[i].s)
{
sum -= q.top();
q.pop();
tot--;
}
ans = max(ans, sum);
}
cout << ans;
return 0;
}
例题 2
贪心，按照坐标排序，如果这个机房可以 AK，那么选择，并加入到大根堆中，否则看如果有的 AK 时间比 AK 当前机房的时间长，可以选择放弃，直到可以选择当前机房，并用 \(ans\) 保存下最佳答案。
Accepted Code
/*Code By Manipula*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct AK{
int x, t;
}a[N];
int indx, ans, now;
bool cmp(AK aa, AK bb){return aa.x < bb.x;}
priority_queue<int> q;
signed main()
{
int n, limit;
cin >> n >> limit;
for (int i = 1; i <= n; i++)cin >> a[i].x >> a[i].t;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
now++; indx += a[i].x - a[i - 1].x + a[i].t; q.push(a[i].t);
while (!q.empty() && indx > limit)
{
now--;
indx -= q.top();
q.pop();
}
if (indx > limit)break;
ans = max(ans, now);
}
cout << ans;
return 0;
}
习题
P3545 [POI2012] HUR-Warehouse Store
再推荐个题单吧 qwq
标签：int,AK,笔记,反悔,ans,例题,贪心 From： https://www.cnblogs.com/Manipula/p/17760728.html