贪心(一):区间问题、Huffman树
2022/1/14 23:10:23
本文主要是介绍贪心(一):区间问题、Huffman树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
区间问题
例题一:区间选点
给定 N 个闭区间 [ai,bi]请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需的点的最小数量。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
输入样例:
3 -1 1 2 4 3 5
输出样例:
2
解题思路:
解题代码:
#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); //把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;//res当前选择点的坐标,ed上一点的坐标 //枚举所有的区间 for(int i=0;i<n;i++) if(range[i].l>ed)//当前区间的左端点严格大于ed,选择一个新点 { res++; ed=range[i].r; } printf("%d\n",res); return 0; }
例题二: 最大不相交区间数量
给定 N 个闭区间 [ai,bi],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。
输出可选取区间的最大数量。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示可选取区间的最大数量。
数据范围
1≤N≤105
−109≤ai≤bi≤109
输入样例:
3 -1 1 2 4 3 5
输出样例:
2
解题思路:
解题代码:
#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; }
例题三:区间分组
给定 N 个闭区间 [ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi表示一个区间的两个端点。
输出格式
输出一个整数,表示最小组数。
数据范围
1≤N≤105
−109≤ai≤bi≤109
输入样例:
3 -1 1 2 4 3 5
输出样例:
2
解题思路:
解题代码:
#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 r=range[i]; //堆是空的,最小值都大于等于左端点,必须开个新的组 if(heap.empty()||heap.top()>=r.l) heap.push(r.r); else//否则就能放到当前组里面去 { heap.pop();//把堆顶删掉 //将新的右端点加入堆里面去 heap.push(r.r); } } //输出样本组的数量 printf("%d\n",heap.size()); return 0; }
例题四:区间覆盖
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 −1
输入格式
第一行包含两个整数 s 和 t,表示给定线段区间的两个端点。
第二行包含整数 N,表示给定区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需最少区间数。
如果无解,则输出 −1
数据范围
1≤N≤105
−109≤ai≤bi≤109
−109≤s≤t≤109
输入样例:
1 5 3 -1 3 2 4 3 5
输出样例:
2
解题思路:
解题代码:
#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; //遍历所有左端点在start左边这些区间右端点最大值是多少 while(j<n&&range[j].l<=st) { r=max(r,range[j].r); j++; } //如果扫描完之后,最大值都小于start则无解 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; }
Huffman树
例题:合并果子
在一个果园里,达达已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并,达达可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。
可以看出,所有的果子经过 n−1 次合并之后,就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使达达耗费的体力最少,并输出这个最小的体力耗费值。
例如有 33 种果子,数目依次为 1,2,9
可以先将 1、2 堆合并,新堆数目为 3,耗费体力为3。
接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12耗费体力为 12
所以达达总共耗费体力=3+12=15
可以证明 15 为最小的体力耗费值。
输入格式
输入包括两行,第一行是一个整数 n,表示果子的种类数。
第二行包含 n 个整数,用空格分隔,第 i 个整数 ai 是第 i 种果子的数目。
输出格式
输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。
输入数据保证这个值小于 231。
数据范围
1≤n≤10000
1≤ai≤20000
输入样例:
3 1 2 9
输出样例:
15
解题思路:
解题代码:
#include <iostream> #include <algorithm> #include <queue> using namespace std; int main() { int n; scanf("%d",&n); priority_queue<int,vector<int>,greater<int>> heap; while(n--)//把每个数都读进来 { int x; scanf("%d",&x); heap.push(x);//读完后,直接插入堆里面 } int res=0;//表示答案 while(heap.size()>1)//堆当中的元素个数大于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; }
这篇关于贪心(一):区间问题、Huffman树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南