>
反悔贪心学习笔记
2022-12-13 学习笔记 约 3.4 千字

贪心获得的局部最优解往往不是全局最优解，在我们需要全局最优解时，就要进行反悔操作。

反悔贪心一般有两种实现方式 - 反悔堆和反悔自动机。

  • 反悔堆：按照某种顺序，依次考虑可能的决策，通过堆来维护当前最优解，如果遇到当前维护的解不是最优的时候，回退之前的某种决策并更新最优解。

  • 反悔自动机：设计一种反悔策略，使得任意一种贪心策略都可以到达最优解。一般是利用差值来实现自动更新最优解。

练习题：

反悔堆：

Supermarket

超市里有 NN 件商品，每件商品都有利润 pip_i 和过期时间 did_i，每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

题目链接: https://www.luogu.com.cn/problem/T290286

题目分析

很容易想到一种贪心策略，对于每一天都卖掉距离过期时间最近的，价值最高的物品，这个贪心明显是错误的，例如下面这个数据：

1 1
4 2
3 2
5 4

如果用上面的贪心策略，得到的收益是 10，但是最高收益显然是 12。

为什么会出现这样的问题呢？因为到了后期，有很多高收益的工作但是时间被低收益的任务填满。因此我们希望抛弃低价值的决策，选择更高价值的决策。

考虑反悔贪心。

对物品按照过期时间排序，依次考虑商品。

用小根堆（以利润为权值）来维护我们要卖的商品。

  1. 当前商品如果过期天数 tt 等于当前堆中的商品数量。表示前 tt 天要卖的东西已经定了。 我们考虑能不能反悔达到更高的利润，当堆顶的商品利润小于当前的商品的利润，则反悔。（删除堆顶并插入当前的商品）

  2. 若当前商品的过期天数大于当前堆内的商品个数，直接把该商品放入堆中。

时间复杂度 O(qnlog⁡n)O(qn \log n)，qq 是数据组数。

Code:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <iomanip>
#include <map>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

const int N = 10010;

#define time first
#define value second

int n, ans;
bool vis[N];
priority_queue<int, vector<int>, greater<int> > q;
PII task[N];

int main() {
	while (cin >> n) {
		memset(vis, 0, sizeof vis);
		ans = 0;
		for (int i = 1; i <= n; i ++ ) {
			task[i].value = read();
			task[i].time = read();
		}
		sort(task + 1, task + n + 1); // 将任务按照截止时间排序
		for (int i = 1; i <= n; i ++ ) {
		    if (task[i].time == q.size()) { // 考虑是否反悔
		        if (task[i].value > q.top()) { // 反悔操作
		            q.pop();
		            q.push(task[i].value);
		        }
		    }
		    else q.push(task[i].value); // 如果当前决定做的任务数小于截止日期也就是还有时间做当前任务
		}
		while (q.size()) {
		    ans += q.top(); q.pop();
		}
		printf("%d\n", ans);
	}
	return 0;
}

Task

有 nn 个任务（n≤105n \le 10^5），每个任务有两个属性：截止日期 did_i 和完成耗时 tit_i。在截止日期前完成任务就可以得到这个任务产生的价值。在同一时间我们只能去做一个任务。所有任务的价值都一样。

求在合理安排任务进行顺序下，最多能完成多少个任务。

题目链接：https://www.luogu.com.cn/problem/P4053

题目分析

有了上题的基础，我们很容易想到使用反悔贪心（反悔堆）。在这题中，我们依然使用堆来维护 “性价比” 最低的任务，反悔贪心策略如下：

对任务按照截止时间排序，依次考虑每件任务。我们用 last 目前堆内任务的总耗时。

  1. 当前商品如果截止时间 d≥d \ge 当前物品的完成耗时 + last，直接把该任务放入堆中。

  2. 否则表示截至 last 要做的任务已经定了。我们考虑能不能反悔以做更多的任务，当堆顶的耗时小于当前的任务的耗时，则反悔。（删除堆顶并插入当前的商品）

答案就是堆中的物品个数。

时间复杂度也是 O(qnlog⁡n)O(qn \log n)。

Code:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <vector>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

#define int long long

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

const int N = 150010;

struct Task {
	int d, l;
	bool operator < (const Task& b) const {
		if (this->d != b.d) return this->d < b.d;
		return this->l < b.l;
	}
} task[N];

priority_queue<int> q;

signed main() {
	int n = read(), last = 0;
	for (int i = 1; i <= n; i ++ ) task[i].l = read(), task[i].d = read();
	sort(task + 1, task + n + 1);
	for (int i = 1; i <= n; i ++ ) {
		if (last + task[i].l <= task[i].d) {
			q.push(task[i].l);
			last += task[i].l;
		}
		else {
			if (q.size() && task[i].l < q.top()) {
				last -= q.top(), q.pop();
				q.push(task[i].l);
				last += task[i].l;
			}
		}
	}
	printf("%lld\n", q.size());
    return 0;
}

反悔自动机

CF865D Buy Low Sell High

已知接下来 nn 天的股票价格，每天可以买入当天的股票，卖出已有的股票，或者什么都不做，求 nn 天之后最大的利润。

题目分析

很容易想到一种贪心策略：把每一天都看作一个物品，从前向后遍历每一天并在所有可选的物品中选择价格最小的，并获得两个股票价格之差的收益。

显然这个贪心是错误的。

例如下面这个数据：

1 2 114514 1919810

如果按照上面的贪心策略，获得的收益是 2-1+1919810-114514=1805297 元，显然我们的最大收益是 114514-1+1919810-2=2034321 元，比错误贪心的答案高了不少。

考虑反悔贪心。

把每一天看成一件物品，将每天的价格 pp 依次加入堆，如果当天可以卖，那么可以获得 pi−ptopp_i - p_{top} 元收益，然后向堆中插入一个价格为 pip_i 元的物品，因为如果在第 ii 天卖出 toptop 天买入的股票不是最优的决策，那么一定未来有第 jj 天满足 aj>aia_j > a_i，我的答案在第 ii 天已经统计了 ai−atopa_i - a_{top}，那么我还需要 aj−aia_j - a_i 达到最优策略，这时在第 jj 天卖出利润为 aia_i 的股票，就相当于补齐了与最优解的差值，从而实现了反悔操作。

上面的数据使用反悔贪心的过程如下（为了好理解，我们用 [] 表示用于反悔的物品）：

heap: 1
ans = 0

heap: 1 2 | a[i] > heap.top, sell heap.top and push(2)
ans = 1

heap: [2] 2 114514 | a[i] > heap.top, sell heap.top and push(114514)
ans = 114514 - 2 + 1 = 114514 - 1 // 反悔操作

heap: 2 [114514] 114514 1919810 | a[i] > heap.top, sell heap.top and push(1919810)
ans = (1919810 - 2) + (114514 - 1)

时间复杂度 O(nlog⁡n)O(n \log n)。

Code:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <vector>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

#define int long long

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

const int N = 300010;

int n, ans, a[N];
priority_queue<int, vector<int>, greater<int>> q;

signed main() {
	n = read();
	for (int i = 1; i <= n; i ++ ) a[i] = read();
	for (int i = 1; i <= n; i ++ ) {
	    q.push(a[i]);
		if (q.size() && a[i] > q.top()) {
			ans += a[i] - q.top();
			q.pop(), q.push(a[i]);
		}
	}
	printf("%lld\n", ans);
    return 0;
}

P1792 [国家集训队]种树

有一个环形的绿化带，有 nn 个位置，顺时针编号 11 到 nn。每个位置有一个价值。有 mm 个树苗，将这些树苗种在这些位置上，相邻位置不能都种。求可以得到的最大值或无解信息。

题目分析

先考虑一条链的情况。

如果 m=1m = 1，那么直接选择序列中最大的数字。

如果 m=2m = 2，有两种情况：

  1. 选择最大值 did_i，然后在除去 di−1,di,di+1d_{i - 1}, d_i, d_{i + 1} 三个数字后剩下的数字中再取一个最大的 djd_j。
  2. 如果上述的 di+dj<di−1+di+1d_i + d_j < d_{i - 1} + d_{i + 1}，那么就选择 di−1d_{i - 1} 和 di+1d_{i + 1}。

引理：在最优解中，最大值两边的数要么同时被选，要么不选。

证明：以后再写。

考虑反悔贪心：

先选择当前最大值，然后当发现选择完最大值产生的结果是不优于同时选择最大值两边的数字时，就放弃最大值，改选最大值两边的数字。

先选择最大值 did_i 后，把 di−1,di,di+1d_{i - 1}, d_{i}, d_{i + 1} 从序列中删除。再把 di+1+di−1−did_{i + 1} + d_{i - 1} - d_{i} 插入序列原位置。接下来就变成了求解在新序列中选择 m−1m - 1 个互不相邻的数字，使得它们的和最大。

  1. 动态序列中快速寻找最大值：大根堆；
  2. 删除、插入操作后保持序列中相对位置关系不变：双向链表。

建立一个链表 list，包含 nn 个节点。每个节点上分别记录下数值 d1,d2,d3…dnd_1, d_2, d_3 \dots d_n。再建立一个大根堆，堆里也有 nn 个数值，并记录下每个数值对应在链表中的节点编号。

  1. 取出堆顶元素 tt，将 tt 的数值累积到答案中，取出 tt 的节点编号 pp。在链表中删除 p→left,p,p→rightp \to left, p, p \to right 节点，在堆中也要删除这些节点。
  2. 假设链表中编号为 pp 的节点存放数值为 value(p)value(p)，那么将 value(p→left)+value(p→right)−value(p)value(p \to left) + value(p \to right) - value(p) 插入到链表中对应的位置。并将其放入堆中。
  3. 重复上述操作 mm 次，输出答案即可。

由于新插入的节点在原来的位置，所以直接修改即可，免去删除的操作。

环形的处理：将 1→left1 \to left 和 n→rightn \to right 分别设为 nn 和 11 即可。

无解的判断：种 mm 棵树需要位置最少的情况是隔一个空位种一棵树，由于是环形，起始或末尾至少有一个空格，所以 n<2mn < 2m 无解。

时间复杂度 O(n+mlog⁡n)O(n + m \log n)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <iomanip>
#include <map>
#include <unordered_map>

using namespace std;

#define int long long

typedef long long ll;
typedef unsigned long long ull;

typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

const int N = 200010;

int n, m, l[N], r[N], d[N];
bool vis[N];

priority_queue<PII> q;

void remove(int x) {
    vis[x] = true;
    l[r[x]] = l[x];
    r[l[x]] = r[x];
}

signed main() {
    n = read(), m = read();
	if (n < m * 2) {
		puts("Error!");
		return 0;
	}
    for (int i = 1; i <= n; i ++ ) d[i] = read();
    for (int i = 1; i <= n; i ++ ) {
        l[i] = i - 1;
        r[i] = i + 1;
        q.push(make_pair(d[i], i));
    }
	l[1] = n, r[n] = 1;
    int ans = 0;
    while (m -- ) {
        while (vis[q.top().second]) q.pop();
        auto t = q.top(); q.pop();
        int v = t.first, p = t.second;
        d[p] = d[l[p]] + d[r[p]] - d[p];
        remove(l[p]), remove(r[p]);
        ans += v;
        q.push(make_pair(d[p], p));
    }
    printf("%lld\n", ans);
    return 0;
}
反悔贪心学习笔记
https://ac.sky390.cn/p/regret-greed-note/
本文作者
Sky390
发布于
2022-12-13
版权协议
转载或引用本文时请遵守许可协议，注明出处、不得用于商业用途！