什么是贪心
贪心：贪心在解决问题上是目光短浅的，仅仅根据当前的已知信息就做出选择，并且一旦做了选择，就不再更改
常见的贪心问题
- 区间问题
- Huffman树
- 排序不等式
- 绝对值不等式
- 推公式
区间问题
区间覆盖
典型题例：
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。
示例 ：
输入：第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。 第二行包含整数 N，表示给定区间数。 接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。 1 5 3 -1 3 2 4 3 5 输出： 2
思路:左端点排序 + 贪心决策
- 将所有区间按照左端点从小到大进行排序
- 从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点的最大值(贪心决策);
代码：
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n; struct Range{ int l, r; bool operator< (const Range&w) const { return l < w.l; } } ranges[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); ranges[i] = {l, r}; } sort(ranges, ranges + n); int ans = 0; bool success = false; for (int i= 0; i < n; i ++) { int j = i, r = -2e9; while (j < n && ranges[j].l <= st) { //找到所有左端点<=st的区间右端点最大的点 r = max(r, ranges[j].r); j ++; } if (r < st) { //肯定有空隙 ans = -1; break; } ans ++; if (r >= ed) { success = true; break; } st = r; //更新st i = j - 1; // } if (!success) ans = -1; printf("%d", ans); }
Huffman树
合并果子
典型题例：
在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。达达决定把所有的果子合成一堆。每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
可以看出，所有的果子经过 n−1 次合并之后，就只剩下一堆了。达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。
例如有 3 种果子，数目依次为 1，2，9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。
所以达达总共耗费体力=3+12=15。
可以证明 15 为最小的体力耗费值。
示例 ：
输入：输入包括两行，第一行是一个整数 n，表示果子的种类数。 第二行包含 n 个整数，用空格分隔，第 i 个整数 ai 是第 i 种果子的数目。。 3 1 2 9 输出： 15
思路
- 使用小根堆维护所有果子，每次弹出堆顶的两堆果子，并将其合并，合并之后将两堆重量之和再次插入小根堆中。
代码：
#include <iostream> #include <queue> #include <algorithm> 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; cin >> x; heap.push(x); } int ans = 0; while (heap.size() > 1) { //堆的个数大于1就需要合并 int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); ans += a + b; heap.push(a + b); } printf("%d", ans); return 0; }
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
