前言
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心问题的解法比较随缘，一般通过猜测加以验证，使局部最优等于全局最优。虽然听起来玄学……
个人博客点这里噢！！
区间问题
区间选点(与下题等价)
给定N个闭区间$[a_i,b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个数量$a_i,b_i$，表示一个区间的两个端点
3
-1 1
2 4
3 5
输出格式
输出一个整数，表示所需的点的最小数量
2
数据范围
$1 \le N \le 10^5$
$-10^9 \le a_i \le b_i \le 10^9$
[HTML_REMOVED]
- 所有区间按照右端点排序
- 枚举每一个区间，如果该区间还未选择点，则选取它的右端点
证明可行性：ans代表选的点的最小值（即答案），cnt代表按照上述方法选取的点的数量
如要证明$ans=cnt$，则需要先后证明$ans\le cnt$和$ans \ge cnt$
要使选取的点覆盖每一个区间，最坏的情况是每一个区间都有一个点，因此$ans \ge cnt$
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range {
int l, r;
bool operator<(const Range & w) const {
return r < w.r;
}
}range[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int a,b;
scanf("%d%d", &a, &b);
range[i] = {a, b};
}
sort(range, range+n);
int res = 0, ed = -2e9;
// 判断为新的区间时，更新区间范围
for (int i = 0; i < n; i++)
if (ed < range[i].l) {
res++;
ed = range[i].r;
}
printf("%d\n", res);
return 0;
}
最不相交区间的数量
给定N个闭区间$[a_i,b_i]$，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取的最大的区间数量。
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个数量$a_i,b_i$，表示一个区间的两个端点
输出格式
输出一个整数，表示可选取区间的最大数量
数据范围
$1 \le N \le 10^5$
$-10^9 \le a_i \le b_i \le 10^9$
cnt代表可行方案。ans代表可行方案中的最大值，也就是答案
-
$ans \ge cnt$：
cnt表示选出的符合条件的所有区间的个数，ans为其中的最大值，因此$ans \ge cnt$ -
$ans \le cnt$：反证法，假设$ans > cnt$，我们一共选出了
cnt个符合条件的区间，意味着有cnt个点存在于区间中（区间选点）。在可以选出比cnt更多的ans个区间的情况下，只存在cnt个点，一个点代表一个区间，那么一定有两个或两个以上的区间有重合的部分，不符合题意，原式得证
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
int l, r;
bool operator<(const Range &w) const {
return r < w.r;
}
}range[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) {
int a, b;
scanf("%d%d", &a, &b);
range[i] = {a, b};
}
sort(range, range+n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
if (ed < range[i].l) {
res++;
ed = range[i].r;
}
printf("%d", res);
return 0;
}
区间分组(小根堆)
给定$N$个闭区间$[a_i,b_i]$，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。输出最小值
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个数量$a_i,b_i$，表示一个区间的两个端点
输出格式
输出一个整数，表示最小组数
数据范围
$1 \le N \le 10^5$
$-10^9 \le a_i \le b_i \le 10^9$
- 将所有区间按照左端点从小到大排序(左端点递增)
- 从前往后处理每个区间，判断其能否放入到现有的组中
L[i] > Max_R - 若满足此条件，将其分给当前区间，并更新右端点
- 若不满足，则要新开一个分组，再将其加入
证明可行性：ans代表最终答案，cnt代表利用上述的算法得到的合法答案：
- $ans \le cnt$：
cnt得到的一定是合法方案，ans为方案中的最小值，因此成立 - $ans \ge cnt$：
cnt个区间都有至少一个公共点，所以要至少要分成cnt个组，所以最终答案ans>=cnt
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator<(const Range& w) const {
return l < w.l;
}
}range[N];
int n;
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.l) heap.push(r.r);
else {
// 合入已有的组，并更新右端点
int t = heap.top();
heap.pop();
heap.push(r.r);
}
}
printf("%d\n", heap.size());
return 0;
}
区间覆盖
给定$N$个闭区间$[a_i,b_i]$以及一个线段区间$[s,t]$，请你选择尽量少的区间，将指定的线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出-1。
输入格式
第一行包括两个整数s和t，表示给定线段区间的两个端点。
第二行包含整数N，表示给定区间数。
接下来N行，每行包含两个整数$a_i,b_i$，表示一个区间的两个端点。
1 5
3
-1 3
2 4
3 5
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出-1。
2
数据范围
$1 \le N \le 10^5$
$-10^9 \le a_i \le b_i \le 10^9$
$-10^9 \le s \le t \le 10^9$
- 将区间按照左端点从小到大排序
- 从前往后依次枚举每个区间，在所有能覆盖
start的区间当中，选择右端点最大的那个区间，并把start更新为这个区间的右端点值
证明可行性：ans代表最终答案，cnt代表利用上述的算法得到的合法答案：
- $ans \le cnt$：
cnt得到的一定是合法方案，ans为方案中的最小值，因此成立 - $ans \ge cnt$：此算法得出的
cnt为最优解，ans因此等于cnt
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
int l, r;
bool operator<(const Range & w) const {
return l < w.l;
}
}range[N];
int main() {
int st, ed;
scanf("%d%d", &st, &ed);
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); // 排序
int res = 0;
bool success = false;
for (int i = 0; i < n; i ++ ) {
int j = i, r = -2e9;
// 找出每一轮区间包含st的最大右端点
while (j < n && range[j].l <= st) {
r = max(r, range[j].r);
j++;
}
if (r < st) {
res = -1;
break;
}
res++;
if (r >= ed) {
success = true;
break;
}
// i在for循环里，最后还要+1，所以如果i=j的话，相当于跳过了一个区间，所以只能i=j-1
i = j - 1;
// 更新start至最大右端点
st = r;
}
if (!success) res = -1;
printf("%d\n", res);
return 0;
}
Huffman树
构造方法：每次选择权值最小的两个点合并
哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
[HTML_REMOVED]
合并果子
有效性证明（两步均用到了贪心）：
- 最小的两个点，深度一定最深，且可以互为兄弟。假设b>f，交换bf的值后
$(3f+2b)-(3b+2f)=3f+2b-3b-2f=f-b<0$，意味着交换后，总权值更小，因此深度一定最深
- 依次将最小的两个点合并，这个过程合理并可以达到最优解
$f(n)=f(n-1)+a+b$，为最小值的点在每步同时减去一个数仍为最小值（转换化第一步）
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int main() {
scanf("%d", &n);
// 小根堆
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < n; i ++ ) {
int x;
scanf("%d", &x);
heap.push(x);
}
int res = 0;
while(heap.size() > 1) {
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
res += a + b;
heap.push(a+b);
}
printf("%d\n", res);
return 0;
}
排序不等式
排队打水
有$n$个人排队到一个水龙头打水，第$i$个人装满水的时间是$t_i$，请问如何安排他们的打水顺序，才能使所有人的等待时间之和最小？
输入格式
第一行包含一个整数$n$
第二行包含$n$个整数，其中第$i$个整数代表第$i$个人装满水桶所花的时间$t_i$
7
3 1 2 6 4 5 7
输出格式
输出一个整数，表示最小的等待时间之和
56
数据范围
$1 \le n \le 10^5$
$1 \le t_i \le 10^4$
$总时间=t_1*(n-1)+t_2*(n-2)+t_3*(n-3)+…$
将打水量从小到大排序，总时间最小。依次算前一位让后面等待的每一位的时间之和
反证法：不是按照从小到大排序，那么存在$t_i>t_{i+1}$
原：$t_i*(t-i)+t_{i+1}*(t-i-1)$
现：$t_{i+1}*(t-i)+t_i*(t-i-1)$
两者相减，得$t_i-t_{i+1}>0$。由此说明如果交换两者后，得到的总时间会更小，得证。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
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); // 1、排序
LL res = 0;
for (int i = 0; i < n; i ++ ) res += t[i] * (n - i - 1); // 计算每一位
printf("%lld\n", res);
return 0;
}
绝对值不等式
货仓选址
$x_1,x_2,x_3,…$分别为数轴上的点，，假设选择$x_t$建点，那么距离之和为
$f(x)=|x_1-x_t|+|x_2-x_t|+…+|x_n-x_t|$
已知当只有两个点时，那么一定是建在两个点之间时，到两点的距离之和最小。
推广到多个点，则应该在所有点的中间时，即为货仓地址
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int x[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &x[i]);
sort(x, x + n);
int res = 0;
for (int i = 0; i < n; i ++ ) res += abs(x[i]-x[n/2]);
printf("%d\n", res);
return 0;
}
推公式
耍杂技的牛
贪心问题的编码比较简单，所以我们严格来说明一下它的推导，来回答为什么这样解是怎么想到的，以及它为什么正确。
根据题意，我们要求的就是找出一种牛的排列方式，令$max(w_1+⋅⋅⋅+w_{i−1}−s_i)$最小，记这个值为$val$。
为了求排序的方案，到底是按重量排，还是按强壮程度排？
可以交换$i$,$i+1$牛的位置，看看满足什么等价条件，就可以使得交换之后$val$更小。
因为只交换两个位置的牛，不会影响到其它位置，所以我们分别计算以下4种情况的$val$，推导结果如下：
| Val | 第$i$个位置上的牛 | 第$i+1$个位置上的牛 |
|---|---|---|
| 交换前 | $w1+w2+…+w_{i-1}-s_i$ | $w1+w2+…+w_{i-1}+w_i-s_{i+1}$ |
| 交换后 | $w1+w2+…+w_{i-1}-s_{i+1}$ | $w1+w2+…+w_{i-1}+w_{i+1}-s_i$ |
观察式子中发现都有$w1+w2+…+w_{i-1}$，于是将其减去，得
| Val | 第$i$个位置上的牛 | 第$i+1$个位置上的牛 |
|---|---|---|
| 交换前 | $-s_i$ | $w_i-s_{i+1}$ |
| 交换后 | $-s_{i+1}$ | $w_{i+1}-s_i$ |
为方便比较，4个式子同时加上$si+s_{i+1}$
| Val | 第$i$个位置上的牛 | 第$i+1$个位置上的牛 |
|---|---|---|
| 交换前 | $s_{i+1}$ | $w_i+si$ |
| 交换后 | $s_i$ | $w_{i+1}+s_{i+1}$ |
已知$w_i+si > s_i$，$w_i+si > w_{i+1}+s_{i+1}$(假设现在是从大到小排序)，我们能够发现，当前一个位置上的$w_i+si$大于后一个位置时，交换后可以得到$val$的最小值，即$max(s_{i+1},w_i+s_i) \ge max(s_i, w_{i+1}+s_{i+1})$，因此我们想到将奶牛按照$w+s$从小到大排序，证毕。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 10;
int n;
vector<PII> v;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) {
int w, s;
scanf("%d%d", &w, &s);
v.push_back({w+s,w});
}
sort(v.begin(), v.end());
int sum = 0, res = -2e9;
for (int i = 0; i < n; i ++ ) {
int w = v[i].second, s = v[i].first - w;
res = max(res, sum - s);
sum += w;
}
printf("%d\n", res);
return 0;
}
