算法学习20：贪心01
前言
提示：以下是本篇文章正文内容：
一、区间问题
1. 区间选点：（右端点）
/*
给定N个闭区间[ai, bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点，输出选择的点的最小数量
输入：
第一行包含N
接下来N行，每行包含2个整数ai, bi，表示一个区间的两个端点
输出：所需点的最小数量
数据范围：1<= N <= 10^5 -10^9 <= ai <= bi <= 10^9
*/
#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 r < W.r;
}
}range[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};
}
// 1.按右端点排序
sort(range, range + n);
int res = 0, ed = -2e9;
for(int i = 0; i < n; i ++)
// 当前区间的左端点 大于 维护的右端点
if(range[i].l > ed)
{
res ++;
ed = range[i].r;// 更新
}
printf("%d\n", res);
return 0;
}
2. 最大不相交区间数量
/*
给定N个闭区间[ai, bi]，请你在数轴上选择若干区间，
使得选中的区间之间互不相交（包括端点）。输出可选取的区间的最大数量。
输入：
第一行包含N，表示区间个数
接下来N行，每行包含2个整数ai， bi，表示一个区间的2个端点。
输出：可选取的区间的最大数量
数据范围：1<= N <= 10^5 -10^9 <= ai<=bi <= 10^9
*/
#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 r < W.r;
}
}range[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);
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;
}
3. 区间分组
/*
给定N个闭区间[ai, bi]，请你将这些区间分为若干组，
使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能的小。
输出最小组数
输入：
第一行包含N，表示区间数
接下来N行，包含2个整数ai，bi，表示一个区间的左右端点
输出：最小组数
数据范围：1<= N <= 10^5 -10^9<= ai<=bi <= 10^9
*/
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n;
// 按照区间左端点排序
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l;
}
}range[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 e = range[i];
// heap为空 或 所有组的右端点的最小值Max_r > e.l
if(heap.empty() || heap.top() >= e.l) heap.push(e.r);// 开新的组
else
{
int t = heap.top();// 有什么用？？？ （好像没有用到！）
heap.pop();// 去堆顶
heap.push(e.r);// 更新当前组
}
}
printf("%d\n", heap.size());
return 0;
}
4. 区间覆盖：
/*
给定N个闭区间[ai, bi]以及一个线段区间[s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖
输出最少的区间数，如果无法完全覆盖则输出-1
输入：
第一行包含2个整数s和t，表示给定线段区间的2个端点
第二行包含整数N
接下来N行，每行包含2个整数ai，bi，表示一个区间的2个端点
输出：
输入一个整数，表示所需要的最少区间数
如果无解，则输出-1
数据范围：
1<= N <= 10^5
-10^9 <= ai, bi <= 10^9
-10^9 <= s, t <= 10^9
*/
#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;
}
} 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;
}
st = r;
i = j - 1;
}
if(!success) res = -1;// 这句有的重复了？？？
printf("%d\n", res);
return 0;
}
二、哈夫曼树
1. 合并果子
/*
有堆果子，要把所有的果子合成一堆。
每一次合并，可以把2堆果子合并到一起，消耗的体力等于2堆果子的重量之和。
可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。
总共消耗的体力等于每次消耗体力之和。
假定每个果子的重量都为1，请你设计出合并的次序方案，是耗费的体力最小，输出这个最小的体力耗费值。
输入：
第一行包含整数n，表示有几堆果子
第二行包含n个整数，第i个整数ai是第i堆果子的数量
输出：
最小的体力耗费值，保证这个值小于2^31
数据范围：
1<=n <= 1000
1 <= ai <= 20000
*/
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
// 定义小顶堆，要加2个参数，规定是这样写的 （也叫优先队列）
priority_queue< int, vector<int>, greater<int> > heap;
while(n --)
{
int x;
scanf("%d", &x);
heap.push(x);
}
int res = 0;
// 只要heap里面的个数 大于2
while(heap.size() > 1)
{
// 弹出最小的2个，压入a+b的和
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
res += a + b;
heap.push(a + b);
}
printf("%d", res);
return 0;
}
总结
提示：这里对文章进行总结：
💕💕💕
