贪心 | 学习笔记

贪心

从局部最优推向全局最优

基本思想

始终做出当前最优选择, 从而期望全局达到最优. 值得注意的是, 如果当前最优选择无法保证推出全局最优解, 我们可以更换策略如动态规划.

贪心证明方式

贪心不证明, 亲人两行泪

1. 反证法: 对于当前的贪心策略, 否定当前的选择来证明是否能达到最优解
2. 构造法: 将问题构造成已知的算法或数据结构从而证明贪心策略正确
3. 数学归纳

反证法的应用实例：田忌赛马

贪心策略：

1. 如果田忌目前的最快🐎快于齐王的最快马, 则两者比
2. 如果田忌的最快马慢于齐王的最快马, 则用田忌的最慢马与齐王的最快马比
3. 如果两者的最快马速度相等, 则：
   1. 若田忌的最慢马快于齐王的最慢马, 则两个最慢马比
   2. 若田忌的最慢马慢于齐王的最慢马或者两者相等, 则用田忌的最慢马与齐王的最快马比

$Solutions$

int l1 = 1, r1 = n, l2 = 1, r2 = n;
// 1 refers to TianJi, 2 refers to the King
sort (hs1 + 1, hs1 + n + 1, greater<int>());
sort (hs2 + 1, hs2 + n + 1, greater<int>());

while (l1 <= r1 && l2 <= r2) {
	if (hs1[l1] > hs2[l2]) l1 ++, l2 ++, mny ++;
	else if (hs1[l1] < hs2[l2]) r1 --, l2 ++, mny --;
	else {
		if (hs1[r1] > hs2[r2]) r1 --, r2 --, mny ++;
		else {
			if (hs1[r1] < hs2[l2]) mny --;
			r1 --, l2 ++;
		}
	}
}
cout << mny * 200 << endl;

最优操作序列的贪心思想: Exchange Argument

经典套路

工序安排问题

单工序 机器不同: HNOI2001 产品加工

双工序 物品相同 机器不同: Product Processing

订单需要完成 $q$ 件产品. 该产品的制作需要经过机器 A 和 机器 B 总共两道工序. 工厂里有 $n$ 个机器 A 以及 $m$ 个机器 B, 都只能同时加工一件产品.

编号为 $i$ 的机器 A, 加工完一件产品（完成产品的第一道工序）需要 $t_i$ 小时, 编号为 $j$ 的机器 B, 加工完一件产品（完成产品第二道工序）需要 $d_j$ 小时.

求最少需要多少时间使全部产品加工完毕.

$q \le 10^6, n, m \le 10^5$.

$Solutions$

由于 $1$ 操作与 $2$ 操作相对独立, 因此可以拆分来看.

对于 $1$ 操作, 直接贪心或二分答案均可:

1.

双工序 第二工序需等待：工序安排

双工序 第二工序无需等待：午餐

仅需一步贪心转化：第二工序时间长的先进行第一工序

剩下的是 $\text{dp}$ 虚晃一枪, 没想到吧

---

区间问题

选择不相交的区间

数轴上有 $n$ 个区间, 每条线段都有起点和终点, 选择最多的不相交的线段个数.

$Solutions$

对右端点进行排序, 一次选择左端点大于前一个已经选择的右端点的区间

区间选点 完全覆盖：雷达安装

数轴上有 $n$ 个闭区间 $[a, b]$ . 取尽可能少的点, 使得每个区间内都至少有一个点 （不同区间内含的点可以是同一个）.

最优的贪心策略为：

右端点升序排列, 右端点相等的左端点降序, 当有区间的左端点大于当前右端点时, 则增加一个新的点

$Solutions$

struct range {
	double l, r;
	bool operator < (const range &t) const {
		if (r != t.r) return r < t.r;
		else return l > t.l;
	}
}nums[N];

int n, d, ans;
cin >> n >> d;
for (int i = 1, x, y; i <= n; ++ i) {
	cin >> x >> y;
	if (y <= d) {
		nums[i].l = x - sqrt(d * d - y * y);
		nums[i].r = x + sqrt(d * d - y * y);
	} else return puts("-1") & 0;
}
sort(nums + 1, nums + n + 1);

int tmpr = nums[1].r;
ans = 1;
for (int i = 2; i <= n; ++ i)
	if (nums[i].l > tmpr) tmpr = nums[i].r, ans ++;
cout << ans << endl;

区间完全覆盖问题

给定 $n$ 个闭区间 $[a, b]$, 选择尽量少的区间覆盖一条指定线段 $[s,t]$.

$Soluitons$

维护一个当前覆盖区间的最右侧端点 $p$. 将所有线段按左端点排序, 每次选择左端点 $\le p$ 且右端点最大的区间即可.

扩展: 线段带权

与贪心关系不大, 见 数据结构优化 dp

区间并集：SDOI2005 区间

给定 $n$ 个闭区间 $[a, b]$ , 求能够覆盖的长度.

贪心策略

1. 按区间左端点排序
2. 动态维护某一区间 $x$, 考虑对下一个区间 $y$ 分类讨论：
   1. $l_x \le l_y$ 且 $r_x \geqslant r_y$
   2. $l_x \le l_y$ 且 $r_x < r_y$
   3. $r_x < l_y$

对于第一种情况：维持原来的起始点 $st$ 和结束点 $ed$ 即可
对于第二种情况：将尾节点更新成 $2$ 区间的尾节点
对于第三种情况：将维护的此区间存入答案, 将 $3$ 区间作为新的动态维护空间

using PII = pair<int, int>;
int n;
vector<PII> segs; // 表示所有区间 

void merge (vector<PII> &segs) {
	vector<PII> ans; // 用于存储合并区间后的结果 
	sort(segs.begin(), segs.end());
	// sort 对 pair 进行排序时, 先根据first关键字排序, 再根据second关键字排序
	int st = -2e9, ed = -2e9;
	// 边界值, 依据题目数据范围而定
	for (auto seg : segs) {
		if (ed < seg.first) {
            if (st != -2e9) ans.push_back({st, ed});
			st = seg.first, ed = seg.second;
        }
		else ed = max(ed, seg.second);
	}
	// merge  
	if (st != -2e9) ans.push_back({st, ed}); // 判空 
	segs = ans; // 更新区间 
}

int main() {
	cin >> n;
	for (int i = 0, l, r; i < n; ++ i) {
		cin >> l >> r;
		segs.push_back({l, r});
	}
	merge(segs);
	cout << segs.size() << endl;
	return 0; 
}

USACO08JAN - Telephone Lines

使用最基础的贪心转化, 即求所有从起点到终点的路径中第 $k + 1$ 条边最短的路径, 考虑到第 $k + 1$ 条边不太好找, 尝试二分答案, 对小于 $mid$ 的边边权赋为 $0$, 大于 $mid$ 的边权赋为 $1$, 意为使当前 $mid$ 成立需要至少有多少条被 $k$ 处理的边, 最短路跑出的 dist[n] 与 $k$ 比较再进行二分即可.

扩展: 反悔贪心

不相邻植树问题

简化题意

在长度为 $n$ 的序列中选 $m$ 个不相邻的元素使权值和最大.

$Solutions$

不难发现选择不相邻元素所能选出的最多元素个数为 $\lceil \frac{n}{2} \rceil$, 即每次间隔 $1$ 个选.

首先有个很假的贪心: 按权值从大到小选, 同时标记当前选的数的左右两边为不可选位置. 如果遇到不可选位置就跳过. 这个贪心可以很轻易被 $\rm hack$:

1 8 9 8 1

以上决策的缺陷在于同时选当前数两边的数后权值有可能比当前数大, 当前一步做出的决策仅对于选当前个数的情况来说是最优的. 于是考虑设计决策使之能够在选更多数的情况下更改前面取到的局部最优解方案.

首先处理权值的反悔. 仍以上面的数据举例, 当从优先队列中取出 $9$ 计入答案后, 向队列中插入权值为 $8 + 8 - 9$ 的点即可, 在下一次选择是会抵消 $9$ 对答案做出的贡献.

然后考虑非法位置如何处理. 当取出 $9$ 时我们标记了两个 $8$ 位置非法, 当改为选 $8$ 时, 需要标记第一个 $8$ 前的 $1$ 和第二个 $8$ 后的 $1$. 考虑使用一个双向链表维护当前位置的前一个位置和后一个位置, 每次选择当前位置时删除当前位置的两侧位置的链表节点即可.

for (int i = 1; i <= n; ++ i) {
	rd(w[i]), pre[i] = i - 1, suf[i] = i + 1;
	q.push({i, w[i]});
}
while (k) {
	int u = q.top().id; q.pop();
	if (st[u]) continue;
	if (w[u] < 0) break;
	k --, st[pre[u]] = st[suf[u]] = true;
	ans += w[u], w[u] = w[pre[u]] + w[suf[u]] - w[u];
	pre[u] = pre[pre[u]], suf[u] = suf[suf[u]];
	suf[pre[u]] = pre[suf[u]] = u;
	q.push({u, w[u]});
}

扩展的扩展: 环形不相邻植树问题

题意基本相同, 只是变为在环上植树. 如果真正理解了上面双向链表的功能, 环形问题应该也是能够迎刃而解的: 将 $pre_1$ 设为 $n$, $suf_n$ 设为 $1$ 即可.