1. 介绍
贪心：即考虑局部最优解达到全局最优解的目的，但有时局部最优解并不会达到全局最优解，此时有两种思考方向，dp和反悔贪心
dp:能全局计算答案，根据拓扑学的DAG实现状态转移达到最优(这里不过多介绍)
反悔贪心：根据之前的决策进行反悔操作，主要用反悔堆实现去除性价比最低的决策，达到最优解
2.例题
1.工作调度
因为本题的完成时间是1，即可以根据截止时间判断前面有无安排满，此时性价比是价格，最低性价比是价格最低的，用小根堆存储，假设当前价格是p，判断是否比堆顶大，假设大，说明选这个比选堆顶的结果大，差值为增加的结果，后把堆顶删去，当前价值加入堆顶代表选了这个价值的工作，方便后面工作判断
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define lowbit(x) (x) & (-x)
#define endl "\n"
#define pb push_back
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
void solve()
{
int n; cin >> n;
vector<ll> d(n + 1), p(n + 1);
vector<PII> pr(n + 1);
ll res = 0;
map<ll, ll> mp;
for(int i = 1; i <= n; i ++) {
cin >> d[i] >> p[i];
pr[i] = {d[i], p[i]};
}
sort(pr.begin() + 1, pr.end());
priority_queue<ll, vector<ll>, greater<>> q;
for(int i = 1; i <= n; i ++){
if(pr[i].first > q.size()) {
res += pr[i].second;
q.push(pr[i].second);
} else {
if(pr[i].second > q.top()) {
res -= q.top();
res += pr[i].second;
q.pop();
q.push(pr[i].second);
}
}
}
//for(auto [u, v] : mp) res += v;
cout << res << endl;
}
signed main()
{
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define lowbit(x) (x) & (-x)
#define endl "\n"
#define pb push_back
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
struct BIT
{
vector<int> tree;
int N;
BIT() {}
BIT(int n){init(n);}
void init(int n) {N = n, tree.resize(n);}
void update(int x, int k){
while (x < tree.size()) {
tree[x] += k;
x += x & -x;
}
}
int query(int x){
int res = 0;
while (x > 0) {
res += tree[x];
x &= x - 1;
}
return res;
}
};
void solve()
{
int n; cin >> n;
vector<ll> d(n + 1), p(n + 1);
vector<PII> pr(n + 1);
ll res = 0;
map<ll, ll> mp;
for(int i = 1; i <= n; i ++) {
cin >> d[i] >> p[i];
d[i] = min(d[i], (int)1e5);
pr[i] = {d[i], p[i]};
}
sort(pr.begin() + 1, pr.end(), [](PII x, PII y) {
return x.second > y.second;
});
BIT bit(100010);
for(int i = 1; i <= n; i ++) {
auto [d, p] = pr[i];
if(bit.query(d) != d) {
int l = 1, r = d;
while(l < r) {
int mid = l + r + 1 >> 1;
if(bit.query(d) - bit.query(mid - 1) != d - mid + 1) l = mid;
else r = mid -1;
}
bit.update(l, 1);
res += p;
}
}
//for(auto [u, v] : mp) res += v;
cout << res << endl;
}
signed main()
{
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}
2.Money Buys Less Happiness Now
题意：开始钱为0，n个月，每月会增加x元，每件商品都有 ai元，在n月内能买多少件
把每次的花费看作性价比，性价比地的就是价格最大的，即用大根堆维护，now代表当前的钱的变化
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define lowbit(x) (x) & (-x)
#define endl "\n"
#define pb push_back
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
void solve()
{
int n, x; cin >> n >> x;
vector<int> a(n + 1);
for(int i = 1; i <= n; i ++) {
cin >> a[i];
}
priority_queue<ll>q;
ll res = 0, now = 0;
for(int i = 1; i <= n; i ++) {
if(now >= a[i]) {
res ++;
q.push(a[i]);
now -= a[i];
} else if(q.size() && q.top() >= a[i]) {
now += q.top();
now -= a[i];
q.pop();
q.push(a[i]);
}
now += x;
}
cout << res << endl;
}
signed main()
{
int T = 1;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
3. 建筑抢修
题意：我们再来考虑这样一个问题，我们有 n 个任务，并且每个任务都有两个属性——截止日期t2和完成耗时t1。在截止日期前完成任务就可以得到这个任务产生的价值。在同一时间我们只能去做一个任务。所有任务的价值都是一样的，问我们最后最多能完成多少个任务。
可以以截至时间排序，now表示当前时间的变化，此时性价比是t1耗时，最低性价比是耗时最大，用大根堆维护，如果now比t2小，直接加上这个贡献放入大根堆，否则此时耗时置换一下堆顶，相当于减去多的耗时，更新now时间
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define lowbit(x) (x) & (-x)
#define endl "\n"
#define pb push_back
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
struct node {
ll st, lst, ed;
bool operator < (const node &_) const {
return ed < _.ed;
}
};
void solve()
{
int n; cin >> n;
vector<node> p(n + 1);
for(int i = 1; i <= n; i ++) {
ll t1, t2; cin >> t1 >> t2;
p[i] = {t2 - t2, t1, t2};
}
ll res = 0;
sort(p.begin() + 1, p.end());
priority_queue<ll> q;
ll now = 0;
for(int i = 1; i <= n; i ++) {
auto [st, lst, ed] = p[i];
if(now + lst <= ed) {
res ++;
q.push(lst);
now += lst;
} else if(now + lst > ed && q.size()) {
if(q.top() > lst) {
now -= q.top();
now += lst;
q.pop();
q.push(lst);
}
}
}
cout << res << endl;
}
int main()
{
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}
4.买卖股票
题意：已知接下来n天的股票价格，每天可以买入当天的股票，卖出已有的股票，或者什么都不做，求n天之后最大的利润。
考虑每一天的股票，如果可以i卖出，则选择之前价格最低的股票j买入 且 ai > aj 考虑用小根堆维护，注意这里有个关系 Csell - Cbuy = (Csell - Ci) + (Ci - Cbuy) Ci 代表任意一天的股票· 我们买价格最小的股票去卖价格最大的股票，以期得到最大的利润。我们先把当前的价格放入小根堆一次（这次是以上文的贪心策略贪心），判断当前的价格是否比堆顶大，若是比其大，我们就将差值计入全局最优解，再将当前的价格放入小根堆（这次是反悔操作）。这种传递关系代表我们把当前的股票价格若不是最优解，就没有用，最后可以得到全局最优解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define lowbit(x) (x) & (-x)
#define endl "\n"
#define pb push_back
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
void solve()
{
int n; cin >> n;
vector<ll> a(n + 1);
for(int i = 1;i <= n; i ++) cin >> a[i];
priority_queue<ll, vector<ll>, greater<>> q;
ll cnt = 0, res = 0;
for(int i = 1; i <= n; i ++) {
q.push(a[i]);
if(q.size() && q.top() < a[i]) {
cnt ++;
res += a[i] - q.top();
q.pop();
q.push(a[i]);
}
}
cout << res << endl;
}
int main()
{
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}