【算法基础】第六章：贪心

Chapter 6 贪心

1：区间选点

给定 N个闭区间 [a,b]，请你在数轴上 选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

区间问题的本质就是排序

按左端点排序
按右端点排序
双关键字排序（先按右端点，再按左端点）

思路：

① 所有区间按右端点从小到大排序

② 遍历每一个区间，如果当前区间的左与前一个区间的右有交集，则只需要一个点就可以覆盖掉两个区间

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;         // 线段数量
int res;       // 结果
int ed = -INF; // 当前覆盖区间的结束边界，即右端点位置// 结构体
struct Node {int l, r;// 按每个区间的右端点从小到大排序const bool operator<(const Node &b) const {return r < b.r;}
} range[N];int main() {cin >> n;// 注意这里的数组下标是从0开始的for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;// 右端点从小到大排序，排序也需要从数组下标1开始sort(range, range + n);for (int i = 0; i < n; i++)if (range[i].l > ed) {res++;ed = range[i].r;}cout << res << endl;return 0;
}

2：最大不相交区间数量

给定 N个闭区间 [a,b]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

思路：

将每个区间按右端点从小到大排序
从前往后依次枚举每个区间

如果当前区间中已经包含点，则直接pass
否则，选择当前区间的右端点。

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;         // 线段数量
int res;       // 结果
int ed = -INF; // 当前覆盖区间的结束边界，即右端点位置// 结构体
struct Node {int l, r;// 强制要求使用这种结构体的排序自定义函数方式// 按每个区间的右端点从小到大排序const bool operator<(const Node &b) const {return r < b.r;}
} range[N];int main() {cin >> n;// 注意这里的数组下标是从1开始的for (int i = 1; i <= n; i++) cin >> range[i].l >> range[i].r;// 右端点从小到大排序，排序也需要从数组下标1开始sort(range + 1, range + n + 1);// 思想：按右端点从小到大排序后，再遍历每一个区间，尽可能取右端点，如果中间出现中断现象，只能再多一个点// 其实，每一个点都可能有多个选择，只要是多个区间的共同点即可，不是唯一点for (int i = 1; i <= n; i++)if (range[i].l > ed) {res++;ed = range[i].r;}cout << res << endl;return 0;
}

3：区间分组

给定 N 个闭区间 [a,b]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得 组数尽可能小。

输出最小组数。

Dilworth定理：最小不相交分组数等于最大相交组的元素个数

可以把这个问题想象成活动安排问题。有若干个活动，第i个活动开始时间和结束时间是[Si,Ei]，同一个教室安排的活动之间不能交叠，求要安排所有活动，至少需要几个教室？

思路1：

把所有开始时间和结束时间排序，遇到开始时间就把需要的教室加1，遇到结束时间就把需要的教室减1，在一系列需要的教室个数变化的过程中，峰值就是多同时进行的活动数，也是我们至少需要的教室数。

#include <bits/stdc++.h>using namespace std;const int N = 100100;int b[2 * N]; // key,value:第几个端点，坐标值
int idx;      // 用于维护数组b的游标
int n;        // 共几个区间
int res = 1;  // 全放到一个组中，最小，默认值1int main() {cin >> n; // n个区间for (int i = 1; i <= n; i++) {int l, r;cin >> l >> r;b[idx++] = l * 2;     // 标记左端点为偶数;同比放大2倍，还不影响排序的位置，牛~b[idx++] = r * 2 + 1; // 标记右端点为奇数;同比放大2倍，还不影响排序的位置，牛~}// 将所有端点放在一起排序，由小到大sort(b, b + idx);int t = 0;for (int i = 0; i < idx; i++) {if (b[i] % 2 == 0)t++; // 左端点+1elset--;           // 右端点-1res = max(res, t); // 动态计算什么时间点时，出现左的个数减去右的个数差最大，就是冲突最多的时刻}// 输出结果cout << res << endl;return 0;
}

思路2：

枚举每个区间，看看当前区间是不是和现有的组存在交集。
如果当前枚举到的这个区间和某一个组没有交集，我们就把他放入这个组内。【即：当前区间左端点大于现在某个组的右端点，我们将这个区间归为这一组，注意更新组的右端点】
如果当前枚举到的这个区间和现有的所有的组都有交集，我们就不能将这个区间归到组内，而是要给他新开一个组。【即，当前区间的左端点小于或等于现有的所有组的右端点，我们就从新开一个组】

#include <bits/stdc++.h>
using namespace std;const int N = 100010;int n;
struct Node {int l, r;const bool operator<(const Node &b) const {return l < b.l; // 按照左端点进行排序}
} range[N];int main() {cin >> n;for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;sort(range, range + n);priority_queue<int, vector<int>, greater<int>> heap; // 我们的小根堆始终保证所有组中的最小的右端点为根节点// 用堆来存储组的右端点for (int i = 0; i < n; i++) {auto t = range[i];if (heap.empty() || heap.top() >= t.l) // 如果当前队列为空，或者区间的端点小于小根堆的根（当前组的最小右端点）heap.push(t.r);                    // 那么这个区间就是一个大佬，和所有组都有仇，自己单开一组else {heap.pop();     // 如果大于组当中的最小右端点，说明它至少肯定和这个组没有交集，没有交集那就把它归到这一组里heap.push(t.r); // 既然大于我们小根堆的根，也就说明把它该归到小根堆根所代表的这一组，根就失去了作用}                   // 我们将根去掉，用新的t.r来放入小根堆里，小根堆替我们自动找到所有组当中为所有组的最小右端点，并作为新根}cout << heap.size() << endl; // 我们就是用size来表示的组的return 0;
}

4：区间覆盖

给定 N个闭区间 [a,b] 以及一个线段区间 [s,t]，请你 选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出−1。

思路：

将所有区间按左端点从小到大排序
从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间，然后将start更新为右端点的最大值

#include <bits/stdc++.h>using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100010;struct Node {int l, r;const bool operator<(const Node &b) const { // 按每个区间的左端点从小到大排序return l < b.l;}
} range[N];int n;      // n个区间
int st, ed; // 开始端点，结束端点
int res;    // 选择的区间数int main() {// 输入cin >> st >> ed >> n;for (int i = 0; i < n; i++) {int l, r;cin >> l >> r;range[i] = {l, r};}// 1、按左端点从小到大排序sort(range, range + n);// 2、遍历每个区间,注意这里的i没有++,因为可能一次跳过多个区间for (int i = 0; i < n;) {int j = i;int r = -INF; // 预求最大，先设最小// 3、双指针，从当前区间开始向后，找出覆盖start起点的区间,就是让区间尽可能的长while (j < n && range[j].l <= st) {r = max(r, range[j].r); // 找出右端最长的那个区间j++;}// 4、如果没有找到，表示出现了空隙if (r < st) {cout << -1 << endl;exit(0);}// 5、如果找到，多找出了一个区间res++;// 6、如果已经完整覆盖,输出if (r >= ed) {cout << res << endl;exit(0);}// 7、更新迭代起点st = r;// 指针跳跃i = j;}// 7、如果运行到这里，表示无法覆盖掉所有点cout << -1 << endl;return 0;
}

5：huffman树——合并果子

在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

达达决定把所有的果子合成一堆。

每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过 n−1 次合并之后，就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1，2，9。

可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。

接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。

所以达达总共耗费体力=3+12=15。

可以证明 15 为最小的体力耗费值。

思路：

huffman tree

每次将最小值的两个节点捏在一起，组成一个新的节点，执行上述操作，直至最后只剩下一个结点

最小值可用小根堆实现

#include <bits/stdc++.h>using namespace std;// 升序队列，小顶堆
priority_queue<int, vector<int>, greater<int>> q;
int res;int main() {int n;cin >> n;while (n--) {int x;cin >> x;q.push(x);}while (q.size() > 1) {int a = q.top();q.pop();int b = q.top();q.pop();res += a + b;q.push(a + b);}cout << res << endl;return 0;
}

6：排队打水

有 n 个人排队到 11 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti ，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

思路：

让最磨叽的人，最后打水，谁快就谁先来，节约大家时间。
$sum=∑_{i=1}^n(n−i+1)∗a[i]$

#include <bits/stdc++.h>using namespace std;
const int N = 100010;typedef long long LL;
int a[N];
LL res;int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];sort(a, a + n);for (int i = 0; i < n; i++) res += a[i] * (n - i - 1);printf("%lld", res);return 0;
}

7：货仓选址

在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得 货仓到每家商店的距离之和最小。

思路：

如果n是奇数，则应该选在中位数

如果n是偶数，则应该选在中间两个数之间

#include <bits/stdc++.h>using namespace std;
const int N = 100010;
int n, res;
int a[N];int main() {cin >> n;for (int i = 0; i < n; i++) cin >> a[i];sort(a, a + n); // 注意下标从0开始for (int i = 0; i < n; i++) res += abs(a[i] - a[n / 2]);printf("%d", res);return 0;
}

8：耍杂技的牛

农民约翰的 N 头奶牛（编号为 1…N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为 风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是 确定奶牛的排序，使得所有奶牛的风险值中的 最大值尽可能的小。

思路：

W是重量，S是强壮程度

按照W+S从小到大的顺序排，最大的危险系数一定是最小的

#include <bits/stdc++.h>using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 50010;
PII cow[N];
int n;int main() {cin >> n;           //奶牛的数量for (int i = 0; i < n; i++) {int s, w;                         //牛的重量和强壮程度cin >> w >> s;cow[i] = {w + s, w};            //之所以这样记录数据，是因为我们找到贪心的公式，按 wi+si排序}//排序sort(cow, cow + n);//最大风险值int res = -INF, sum = 0;for (int i = 0; i < n; i++) {int s = cow[i].first - cow[i].second, w = cow[i].second;res = max(res, sum - s); //res为最大风险值sum += w;                //sum=w1+w2+w3+...+wi}printf("%d\n", res);return 0;
}