北京外贸网站开发广告推广宣传
看文先三连，养成好习惯~看文先三连，养成好习惯~看文先三连，养成好习惯~
目录
知识点：
堆排序：
优先队列：
定义：（默认大顶堆）
入队:
出队：
取队顶：
求长度：
是否为空：
堆的应用：
前缀编码：
带权路径和；
~题题题题~
哈夫曼树
题目描述
输入描述
输出描述
样例输入
样例输出
代码
supermarket
题目描述
输入描述
输出描述
样例输入
样例输出
代码
序列合并
题目描述
输入描述
输出描述
输入样例
输出描述
代码
合并果子
题目描述
输入描述
输出描述
样例输入
输出
提示
代码
这是最后一节贪心，下节课就要开启长达6666666节课的DP
知识点：
堆排序：
时间复杂度：O(nlogn)
优先队列：
优先队列是容器，大/小顶堆是内部实现方法
定义：（默认大顶堆）
priority_queue<int>Q;//int也可以换成string、double······
priority_queue<int,vector<int>,greater<int> >q;//两个尖括号之间要空格！！！否则编译错误！！！
入队:
Q.push(x);
出队：
Q.pop();
取队顶：
Q.top();
求长度：
Q.size();
是否为空：
Q.empty();
堆的应用：
前缀编码：
按出现频率构造二叉树，左0右1
频率高用短码，频率低用长码
带权路径和；
~题题题题~
哈夫曼树
题目描述
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入描述
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出描述
输出权值。
样例输入
2 2 8 3 5 11 30
样例输出
10 62
代码
#include<iostream>
#include<queue>
using namespace std;
int n,a[1005];
int h,sum;
int main(){while(cin>>n){priority_queue<int,vector<int>,greater<int> >q;h=0;sum=0;for(int i=1;i<=n;i++){cin>>a[i];q.push(a[i]);}while(q.size()>1){int x=q.top();//最小 q.pop();int y=q.top();//次小 q.pop();h=x+y;q.push(h);sum+=h;}cout<<sum<<"\n";}return 0;
} supermarket
题目描述
超市里有N件商品，每个商品都有利润pi和过期时间di,每天只能卖一件商品, 卖掉一件物品要用 1 的时间 ，过期商品（即当天di<=0）不能再卖。求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
0≤N≤100000
1≤pi,di≤10000
输入描述
每组数据一行，首先一个整数 n然后 n 对数 p_i,d_i，以文件终止符结束。
输出描述
对每组数据，输出最佳收益。
样例输入
4 50 2 10 1 20 2 30 1 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
样例输出
80 185
代码
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,sum;
struct aaa{int p,d;
}a[100005];
bool cmp(aaa a,aaa b){//1不换，0换 return a.d<b.d;
}
int main(){while(cin>>n){sum=0;priority_queue<int,vector<int>,greater<int> >q;for(int i=1;i<=n;i++){cin>>a[i].p>>a[i].d;}sort(a+1,a+n+1,cmp);//按日期从小到大排 for(int i=1;i<=n;i++){q.push(a[i].p);//利润入小顶堆 if(a[i].d<q.size()){//出队最小值 q.pop();}}while(!q.empty()){sum+=q.top();q.pop();}cout<<sum<<"\n";} return 0;
}序列合并
题目描述
有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。
输入描述
第一行一个整数N（0≤N≤1050≤N≤105)
第二行N个整数Ai，满足Ai <= 1e9
第三行N个整数Bi，满足Bi <= 1e9
输出描述
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
输入样例
3
2 6 6
1 4 8
输出描述
3 6 7
代码
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int n;
int a[100005],b[100005],ans[100005];
priority_queue<int>q;//大顶堆
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}sort(a+1,a+n+1);sort(b+1,b+n+1);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x=a[i]+b[j];if(q.size()<n){q.push(x);}else{if(q.top()>x){q.push(x);q.pop();}else{break;}}}}for(int i=1;i<=n;i++){ans[i]=q.top();q.pop();}for(int i=n;i>=1;i--){cout<<ans[i]<<" ";}return 0;
} 合并果子
题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入描述
输入包括两行，第一行是一个整数n(1< ＝n< =10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1< ＝ai< =20000)是第i种果子的数目。
输出描述
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^31。
样例输入
3 1 2 9
输出
15
提示
对于30％的数据，保证有n< =1000： 对于50％的数据，保证有n< =5000； 对于全部的数据，保证有n< =10000。
代码
#include<iostream>
#include<queue>
using namespace std;
int n,a[10005];
int h,sum;
int main(){while(cin>>n){priority_queue<int,vector<int>,greater<int> >q;h=0;sum=0;for(int i=1;i<=n;i++){cin>>a[i];q.push(a[i]);}while(q.size()>1){int x=q.top();//最小 q.pop();int y=q.top();//次小 q.pop();h=x+y;q.push(h);sum+=h;}cout<<sum<<"\n";}return 0;
} //跟第一题像到极致！！！！！！！！！！！
创作不易，点个关注吧~创作不易，点个关注吧~创作不易，点个关注吧~