算法基础课 贪心算法模板题笔记

AcWing算法基础课 贪心算法模板题笔记

贪心得到的答案 >= 最优解
贪心得到的答案 <= 最优解

局部最优 -> 全局最优

1 区间问题

排序 + 维护端点

例1：区间选点

AcWing 905. 区间选点

核心思路：维护右端点，判断区间不相交——某区间的左端点大于当前维护区间的右端点

1. 将每个区间按右端点从小到大排序
2. 从前往后依次枚举每个区间
   • 若所枚举区间已包含当前区间的点，则直接pass
   • 否则选择当前区间的右端点

理由：若当前区间存在点包含于所枚举区间，则其中必有其右端点，越靠右越有可能被更多的区间包含。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n;
PII range[N];	// (l, r)

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		range[i] = {l, r};
	}
	
	sort(range, range + n, [](PII &a, PII &b) {
		return a.second < b.second;
	});
	
	int res = 0, ed = -2e9;
	for (int i = 0; i < n; i++)
		if (range[i].first > ed) {	// 若不相交（左>当前右）
			res++;	// 选取当前右端点
			ed = range[i].second;	// 结束维护，转移至所枚举区间
		}
	printf("%d\n", res);
	
	return 0;
}

例2：最大不相交区间数量

AcWing 908. 最大不相交区间数量

（核心思路与实际所求的局部最值和上一题完全相同）

1. 将每个区间按右端点从小到大排序
2. 从前往后依次枚举每个区间
   • 若所枚举区间已包含当前区间的点，则直接pass
   • 否则选择当前区间的右端点

理由：若当前区间的右端点不包含于所枚举区间，则该两区间必定不相交，故可选择当前区间（实为从当前区间及与其重合的任意区间中任选一）。

/* 同上一例 */
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n;
PII range[N];	// (l, r)

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		range[i] = {l, r};
	}
	
	sort(range, range + n, [](PII &a, PII &b) {
		return a.second < b.second;
	});
	
	int res = 0, ed = -2e9;
	for (int i = 0; i < n; i++)
		if (range[i].first > ed) {	// 若不相交（左>当前右）
			res++;	// 选取当前区间
			ed = range[i].second;	// 结束维护，转移至所枚举区间
		}
	printf("%d\n", res);
	
	return 0;
}

例3：区间分组

AcWing 906. 区间分组

核心思路：同时维护多个右端点，更新其最值

1. 将每个区间按左端点从小到大排序
2. 从前往后处理每个区间：判断能否将其放到某个现有的组中，即其是否与组内最右区间无交集
   • 若不存在这样的组，则开新组放此区间
   • 若存在这样的组，则将其放入并更新

可用小根堆快速筛出目前最右区间的右端点最小的组，若满足要求则删除堆顶并将当前区间右端点插入，最终堆中元素个数即为组数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n;
PII range[N];	// (l, r)

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		range[i] = {l, r};
	}
	
	sort(range, range + n);
	
	priority_queue<int, vector<int>, greater<int> > heap;
	for (int i = 0; i < n; i++) {
		auto &r = range[i];
		if (heap.empty() || heap.top() >= r.first) heap.push(r.second);	// 不满足要求则直接插入
		else {	// 满足要求则删除堆顶后再插入
			heap.pop();
			heap.push(r.second);
		}
	}
	
	printf("%d\n", heap.size());
	
	return 0;
}

例4：区间覆盖

AcWing 907. 区间覆盖

核心思路：覆盖起点，更新起点

1. 将每个区间按左端点从小到大排序
2. 从前往后依次枚举每个区间，在所有能覆盖 $s$ 的区间中，选右端点最大的区间（覆盖最多）；然后将 $s$ 更新成右端点的最大值
   • 若不存在能覆盖 $s$ 的区间，则一定会出现空隙，必无解

理由：选择区间数最少 = 起点 $s$ 被赶至终点 $t$ 所需次数最少

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n;
PII range[N];
int S, T;

int main() {
	scanf("%d%d%d", &S, &T, &n);
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		range[i] = {l, r};
	}
	
	sort(range, range + n);
	
	int res = 0;
	bool success = false;
	for (int i = 0; i < n;) {
		int j = i, max_r = -2e9;
		while (j < n && range[j].first <= S) {	// 找左端点不超过S的区间的最远右端点
			max_r = max(max_r, range[j].second);
			j++;
		}
		
		if (max_r < S) break;	// 最短右端点小于S则说明无法覆盖，必无解
		
		res++;
		S = max_r;
		if (S >= T) {
			success = true;
			break;
		}
		
		i = j;
	}
	
	if (!success) res = -1;
	printf("%d\n", res);
	
	return 0;
}

2 Huffman树

带权路径最短

例：合并果子

AcWing 148. 合并果子

核心思想：每次挑出值最小的合并——建立哈夫曼树

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

int n;
priority_queue<int, vector<int>, greater<int> > heap;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		heap.push(x);
	}
	
	int res = 0;
	while (heap.size() > 1) {
		int x1 = heap.top();
		heap.pop();
		int x2 = heap.top();
		heap.pop();
		
		res += x1 + x2;
		heap.push(x1 + x2);
	}
	
	printf("%d\n", res);
	
	return 0;
}

3 排序不等式

排序

例：排队打水

AcWing 913. 排队打水

核心思想：将所有数从小到大排序，等待时间之和最小，为 ${\sum }_{i=1}^n{t}_i\times (n-i)$ 。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n;
int t[N];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &t[i]);
	
	sort(t, t + n);
	
	long long res = 0;
	for (int i = 0; i < n; i++) res += (long long)t[i] * (n - 1 - i);
	printf("%lld\n", res);
	
	return 0;
}

4 绝对值不等式

三角不等式：$||a|-|b||\le |a\pm b|\le |a|+|b|$

常见题型：求 $f(x)=|x_1-x|+|x_2-x|+\cdots +|x_n-x|(x_1\le x_2\le \cdots \le x_n)$ 的最值。

例：货仓选址

AcWing 104. 货仓选址

由绝对值三角不等式得 $|a-x|+|b-x|\ge |a-b|$ ，当且仅当 $x\in [a,b]$ 时取得等号。要求 $f(x)$ 的最小值，对其两两分组后放缩得$$\begin{array}{rl}f(x)& =(|x_1-x|+|x_n-x|)+(|x_2-x|+|x_{n-1}-x|)+\cdots \\ & \ge (x_n-x_1)+(x_{n-1}-x_2)+\cdots \end{array}$$ 逐项逼近最终可得：$f(x)$ 取得最小值时，$x$ 为有序数列 $x_1,x_2,\cdots ,x_n$ 的中点——当 $n$ 为奇数时，$x=x_{\frac{n+1}{2}}$（即为中位数）；当 $n$ 为偶数时，$x=x_{\frac{n}{2}}$ 或 $x=x_{\frac{n}{2}+1}$。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	sort(a, a + n);
	
	int res = 0;
	for (int i = 0; i < n; i++) res += abs(a[i] - a[n / 2]);
	
	printf("%d\n", res);
	
	return 0;
}

5 推公式

例：耍杂技的牛

AcWing 125. 耍杂技的牛

思路：越重、越强壮的越应放下面，故按 $w_i+s_i$ 从小到大排序，表示从上到下堆叠。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

const int N = 5e4 + 10;

int n;
PII cow[N];		// (w_i, s_i)

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d%d", &cow[i].first, &cow[i].second);
	
	sort(cow, cow + n, [](PII &a, PII &b) {
		return a.first + a.second < b.first + b.second;
	});
	
	int res = -2e9, sum = 0;
	for (int i = 0; i < n; i++) {
		res = max(res, sum - cow[i].second);
		sum += cow[i].first;
	}
	
	printf("%d\n", res);
	
	return 0;
}