二叉堆题目

2024-09-04 05:32
文章标签 题目 二叉

本文主要是介绍二叉堆题目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P3378 【模板】堆

方法一

#include <bits/stdc++.h>
using namespace std;
int n, op, tot, x, hp[1000010];
//往堆里push一个数x，并且形成新的小根堆 
void pus(int x)
{tot++;hp[tot]=x;	//将新加进来的数字放在堆的最后个位置 int now=tot;while(now>1){	 //然后开始往上冒 if(hp[now/2]>hp[now]){	//如果父节点大于当前节点，则交换 swap(hp[now/2], hp[now]);now=now/2;} else	break;	//否则说明找到了自己的位置，已经形成小根堆 }
}
//删除堆顶元素，并且形成新的小根堆 
void del()
{hp[1]=hp[tot];tot--;	//将堆最后一个数放到堆顶，然后往下沉int now=1;
//	while(now<tot){	//这样写，第4个测试点过不去，因为当now=tot-1时，已经没有子节点了，//但是下面计算会找一个子结点，子结点的值为0，比hp[now]的值更小，//这时候便把hp[now]的值替换为0了。下一次pus更新时，堆顶变为0 while(now*2<=tot){	//如果有子节点 int target=2*now;if(target+1<=tot && hp[target+1]<hp[target]){	//如果有右儿子，并且右儿子比左儿子更小 target++;	//则右儿子变为和父结点now比较的选手 }if(hp[target]<hp[now]){	//如果儿子比父结点小，交换 swap(hp[target], hp[now]);now=target;	//下沉 } else	break;	//已经找到自己的位置，新的小根堆已经形成 } 
}
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d", &op);if(op==1){scanf("%d", &x);pus(x);}else if(op==2){printf("%d\n", hp[1]);}else if(op==3){del();}}return 0;	
}

方法二

#include<bits/stdc++.h>
using namespace std;
int n;
multiset<int> ms;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){int a;scanf("%d",&a);if(a==1){int b;scanf("%d",&b);ms.insert(b);}if(a==2){
//			multiset<int>::iterator it=ms.begin();printf("%d\n",*ms.begin());}if(a==3){
//			multiset<int>::iterator it=ms.begin();ms.erase(ms.begin());}}return 0;
}

P1631 序列合并

方法一

#include <bits/stdc++.h>
using namespace std;
int n, a[100010], b[100010], ans[100010], cnt;
priority_queue<int> q;
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d", &a[i]);}for(int i=1; i<=n; ++i){scanf("%d", &b[i]);}for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j){if(q.size()<n){q.push(a[i]+b[j]);}else{if(a[i]+b[j]<q.top()){q.pop();q.push(a[i]+b[j]);}else{break;}}}}while(!q.empty()){ans[++cnt]=q.top();q.pop();}for(int i=n; i>=1; --i){printf("%d ", ans[i]);}return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
int n, a[100010], b[100010], sum[2000010], cnt;
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d", &a[i]);}for(int i=1; i<=n; ++i){scanf("%d", &b[i]);}for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j){if(i*j<=n){cnt++;sum[cnt]=a[i]+b[j];}else{break;}}}sort(sum+1, sum+cnt+1);for(int i=1; i<=n; ++i){printf("%d ", sum[i]);}return 0;
}

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

#include<bits/stdc++.h>
using namespace std;
int n, x, ans, cur;
multiset<int> s;
multiset<int>::iterator asd;
int main(){scanf("%d", &n);//nlogn复杂度 for(int i=1; i<=n; ++i){	scanf("%d", &x);s.insert(x);	//将元素插入到multiset中 }for(int i=1; i<n; ++i){		//总共n-1次即可 //每次选最小的两个合并cur=0;	 		//当前两个果子的和 //找出multiset中当前最小的值 	O(1)的复杂度 cur+=*s.begin();		//将它的值加到cur中 s.erase(s.begin());		//将最小的值删掉 				O(logn)的复杂度 //找出multiset中当前最小的值 	O(1)的复杂度 cur+=*s.begin();s.erase(s.begin());		//将最小的值删掉 				O(logn)的复杂度 ans+=cur;				//加到答案里 s.insert(cur);			//将大果子插入到multiset中 }printf("%d", ans);return 0;
}

P1334 瑞瑞的木板

合并果子双倍经验

#include <bits/stdc++.h>
using namespace std;
int n, l, a, b;
long long ans;
priority_queue<int, vector<int>, greater<int> > q;
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d", &l);q.push(l);}for(int i=1; i<=n-1; ++i){a=q.top();q.pop();b=q.top();q.pop();ans+=a+b;q.push(a+b);}printf("%lld", ans);return 0;
}

P1168 中位数P3871 [TJOI2010]中位数

#include <bits/stdc++.h>
using namespace std;
int n, x;
priority_queue<int> bigheap;
priority_queue<int, vector<int>, greater<int> > smallheap;
int main()
{scanf("%d", &n);scanf("%d", &x);bigheap.push(x);	//大根堆，存放中位数 printf("%d\n", bigheap.top());for(int i=2; i<=n; ++i){scanf("%d", &x);//新的这个数小于大根堆堆顶元素，说明在中位数的左边 if(x<=bigheap.top()){	bigheap.push(x); }else{	//否则说明大于中位数，放在小根堆中，小根堆存放的是大于中位数的数字 smallheap.push(x);}if(i&1){	//如果i是奇数，说明要输出中位数了 while(bigheap.size()!=smallheap.size()+1){if(bigheap.size()>smallheap.size()+1){	//如果大根堆中数太多了 //将大根堆堆顶的数转到小根堆中smallheap.push(bigheap.top());bigheap.pop();	 }else if(bigheap.size()<smallheap.size()+1){	//如果小根堆中数太多了 //将小根堆堆顶的数转到大根堆中bigheap.push(smallheap.top());smallheap.pop();	 }}printf("%d\n", bigheap.top());} }return 0;
}

P3871 [TJOI2010]中位数

#include <bits/stdc++.h>
using namespace std;
int n, m, tot, a;
string opt;
priority_queue<int> big;	//大根堆 
priority_queue<int, vector<int>, greater<int> > small;	//小顶堆 
int main()
{scanf("%d", &n);scanf("%d", &a);big.push(a);for(int i=2; i<=n; ++i){scanf("%d", &a);if(a<=big.top())big.push(a);	//放到大根堆中 elsesmall.push(a);	//放到小根堆中 } tot=n;scanf("%d", &m);for(int i=1; i<=m; ++i){cin>>opt;if(opt=="add"){scanf("%d", &a);tot++;if(a<=big.top())big.push(a);	//放到大根堆中 elsesmall.push(a);	//放到小根堆中 }else if(opt=="mid"){if(tot&1){	//如果有奇数个数，则让大根堆中的数比小根堆中的数多一个，大根堆堆顶即为中位数 while(big.size()!=small.size()+1){if(big.size()>small.size()+1){small.push(big.top());big.pop();}else if(big.size()<small.size()+1){big.push(small.top());small.pop();}} printf("%d\n", big.top());}else{	//如果有偶数个数，则让大根堆中的数和小根堆中的数一样多，两个堆堆顶最小值即为中位数 while(big.size()!=small.size()){if(big.size()>small.size()){small.push(big.top());big.pop();}else if(big.size()<small.size()){big.push(small.top());small.pop();}} printf("%d\n", min(big.top(), small.top()));}}} return 0;
}

P2085 最小函数值

#include <bits/stdc++.h>
using namespace std;
int n, m, a[10010], b[10010], c[10010], f, ans[10010];
priority_queue<int> q;
int main()
{scanf("%d %d", &n, &m);for(int i=1; i<=n; ++i){scanf("%d %d %d", &a[i], &b[i], &c[i]);}for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){f=a[i]*j*j+b[i]*j+c[i];if(q.size()<m){q.push(f);}else{if(f>=q.top()){break;}else{q.pop();q.push(f);}}}}for(int i=1; i<=m; ++i){ans[i]=q.top();q.pop();}for(int i=m; i>=1; --i){printf("%d ", ans[i]);}return 0;
}

P1801 黑匣子

方法一：对顶堆

#include <bits/stdc++.h>
using namespace std;
int n, m, a[200010], u[200010], temp;
//小根堆 
priority_queue<int, vector<int>, greater<int> > small;
//大根堆 
priority_queue<int> big;
int main()
{//m和n，表示元素的个数和GET命令的个数scanf("%d %d", &m, &n);		for(int i=1; i<=m; ++i){scanf("%d", &a[i]);}for(int i=1; i<=n; ++i){scanf("%d", &u[i]);}for(int i=1; i<=n; ++i){for(int j=u[i-1]+1; j<=u[i]; ++j){if(big.size()<i){big.push(a[j]);	if(small.size()!=0 && small.top()<big.top()){temp=big.top();small.push(temp);big.pop();temp=small.top();big.push(temp);small.pop();}} else{small.push(a[j]);if(small.top()<big.top()){temp=big.top();small.push(temp);big.pop();temp=small.top();big.push(temp);small.pop();}}} while(big.size()<i){big.push(small.top());small.pop();}printf("%d\n", big.top());}return 0;
}

中位数思路

#include<bits/stdc++.h>
using namespace std;
priority_queue<int>big;
priority_queue<int,vector<int>,greater<int> >small;
int n,q,i,x,j=1,tot=0;
int num[200005];
int main(){scanf("%d%d",&n,&q);for(i=1;i<=n;i++){scanf("%d",&num[i]);}for(i=1;i<=q;i++){scanf("%d",&x);tot++;while(big.size()+small.size()<x){if(big.empty()){big.push(num[j]);}else{if(num[j]<=big.top()){big.push(num[j]);}else{small.push(num[j]);}}j++;}while(big.size()>tot){small.push(big.top());big.pop();}while(big.size()<tot){big.push(small.top());small.pop();}printf("%d\n",big.top());}return 0;
}

方法二：multiset

#include <bits/stdc++.h>
using namespace std;
int n, m, a[200010], u[200010];
multiset<int> ms;
multiset<int>::iterator asd; 
int main()
{//m和n，表示元素的个数和GET命令的个数scanf("%d %d", &m, &n);		for(int i=1; i<=m; ++i){scanf("%d", &a[i]);}for(int i=1; i<=n; ++i){scanf("%d", &u[i]);}for(int i=1; i<=n; ++i){if(i==1){for(int j=u[i-1]+1; j<=u[i]; ++j){ms.insert(a[j]);} asd=ms.begin();printf("%d\n", *asd);} else{for(int j=u[i-1]+1; j<=u[i]; ++j){ms.insert(a[j]);if(a[j]<*asd){asd--;}}asd++;printf("%d\n", *asd);}}return 0;
}

P2278 [HNOI2003]操作系统

二叉堆、优先队列运算符重载

#include <bits/stdc++.h>
using namespace std;
int curtime;
struct node
{int id;			//进程号 int arrival;	//到达时间 int needtime;	//执行时间 int leval;		//优先级	bool operator < (const node &a)const{if(leval==a.leval){		//到达时间从小到大排序 return this->arrival>a.arrival; }else{		//优先级从大到小排序 return this->leval<a.leval;}} 
}asd, temp;
//优先队列 
priority_queue<node> q;
int main()
{while(scanf("%d %d %d %d", &asd.id, &asd.arrival, &asd.needtime, &asd.leval)!=EOF){//优先队列中没有进程任务 if(q.empty()){q.push(asd);	//入队 curtime=asd.arrival;	//更新当前时间	}else{//在新的进程来之前, 堆顶旧的进程可以执行完 while(!q.empty() && asd.arrival>=curtime+q.top().needtime){printf("%d %d\n", q.top().id, curtime+q.top().needtime); //更新当前时间 curtime=curtime+q.top().needtime; //进程出队 q.pop(); }//如果全部执行完了if(q.empty()){q.push(asd);curtime=asd.arrival;}else{	//在新的进程来了，堆顶旧的进程执行不完//更新堆顶进程的执行需要时间 temp=q.top(); temp.needtime-=asd.arrival-curtime;q.pop();q.push(temp);//更新当前时间 curtime=asd.arrival;//新的进程进入优先队列 q.push(asd); 	}}}//可能最后一个进程入队后, 都每行执行完, 每次执行堆顶进程 while(!q.empty()){printf("%d %d\n", q.top().id, curtime+q.top().needtime); curtime+=q.top().needtime; q.pop(); }return 0;
}

P1878 舞蹈课

#include <bits/stdc++.h>
using namespace std;
int n, a[200010], u, v, cnt, ans1[200010], ans2[200010], before, nxt;
char s[200010];
bool vis[200010];	//false表示 该人还没有匹配到舞伴
struct node1
{int l, r;	
}neighbor[200010]; 
struct node
{int id1, id2, value;	//左侧舞伴序号、右侧舞伴序号、舞伴技术相差值 //运算符重载 bool operator < (const node & x) const{//如果舞伴技术相差值相等时, 根据左侧舞伴序号从小到大排 if(value==x.value){return id1>x.id1;}else{	//如果舞伴技术相差值不相等时, 根据舞伴相差值从小到大排 return value>x.value;}}
}partner[200010];
priority_queue<node> q;
int main()
{scanf("%d", &n);scanf("%s", s);for(int i=1; i<=n; ++i){scanf("%d", &a[i]);neighbor[i].l=i-1;neighbor[i].r=i+1;}for(int i=1; i<n; ++i){if(s[i-1]!=s[i]){	//如果相邻为异性//将这一队舞伴的信息添加到优先队列中 q.push(node{i, i+1, abs(a[i]-a[i+1])});}}while(!q.empty()){u=q.top().id1;	//左侧舞伴序号 v=q.top().id2;	//右侧舞伴序号 if(vis[u] || vis[v]){	//只要有一个舞伴之前配对了, 该对舞伴信息就无效了 q.pop();}else{cnt++;vis[u]=vis[v]=true;		//标记 ans1[cnt]=u;ans2[cnt]=v;q.pop();				//先出队 //找到u左侧的邻居 before=neighbor[u].l;
//			while(vis[before]){
//				before=neighbor[before].l;
//			}//找到v右侧的邻居 nxt=neighbor[v].r;
//			while(vis[nxt]){
//				nxt=neighbor[nxt].r;
//			}if(before>=1 && before<=n && nxt>=1 && nxt<=n){neighbor[before].r=nxt;neighbor[nxt].l=before;if(s[before-1]!=s[nxt-1]){q.push(node{before, nxt, abs(a[before]-a[nxt])});}}}}printf("%d\n", cnt);for(int i=1; i<=cnt; ++i){printf("%d %d\n", ans1[i], ans2[i]);}return 0;
}

这篇关于二叉堆题目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1135129。

相关文章

题目1254：N皇后问题

题目1254：N皇后问题

题目1254：N皇后问题 时间限制：1 秒 内存限制：128 兆 特殊判题：否 题目描述： N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。 你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入
阅读更多...
题目1380：lucky number

题目1380：lucky number

题目1380：lucky number 时间限制：3 秒 内存限制：3 兆 特殊判题：否 提交：2839 解决：300 题目描述： 每个人有自己的lucky number，小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话，都是他的lucky number。但是，现在这个序列很大，他无法快速找到所有lucky number。既然
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
码蹄集部分题目（2024OJ赛9.4-9.8；线段树+树状数组）

码蹄集部分题目（2024OJ赛9.4-9.8；线段树+树状数组）

1🐋🐋配对最小值（王者；树状数组） 时间限制：1秒 占用内存：64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que
阅读更多...
2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 （请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”） 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及， 以及人们活动范围的不断扩大，城市道 路交通拥堵问题日渐严重，即使在一些非中心城市，道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”，是相关部门的棘手难题之一。 考虑一个拥有知名景区
阅读更多...
力扣 739. 每日温度【经典单调栈题目】

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意： 1.1. 给一个温度集合， 要返回一个对应长度的结果集合， 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差， 若是当前元素不存在下一个更高温度的元素， 则这个位置用0代替； 2. 思路 本题用单调栈来求解；单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素；【单调栈：让栈中的元素保持单调
阅读更多...
msyql执行效率的问题以及常见基础面试题目

msyql执行效率的问题以及常见基础面试题目

SQL被称为结构化查询语言(Structured Query Language )是操作和检索关系型数据库的标准语言 SQL语言包括三种主要程序设计语言类别的语句：数据定义语言(DDL)，数据操作语言(DML)及数据控制语言(DCL)。 ※ 数据定义语言(DDL)，例如：CREATE、DROP、ALTER等语句。 　　 Data Definition Language ※ 数据
阅读更多...
2024 年高教社杯全国大学生数学建模竞赛题目【A/B/C/D/E题】完整论文+代码+结果

2024 年高教社杯全国大学生数学建模竞赛题目【A/B/C/D/E题】完整论文+代码+结果

编辑 2024国赛A题参考论文https://download.csdn.net/download/qq_52590045/897183672024国赛D题参考论文https://download.csdn.net/download/qq_52590045/897158482024国赛E题参考论文https://download.c
阅读更多...
2024 年高教社杯全国大学生数学建模竞赛题目【A/B/C/D/E题】完整论文+代码结果

2024 年高教社杯全国大学生数学建模竞赛题目【A/B/C/D/E题】完整论文+代码结果

2024国赛C题参考论文https://download.csdn.net/download/qq_52590045/89718370网盘链接形式，在里更新 2024国赛A题参考论文https://download.csdn.net/download/qq_52590045/89718367      网盘链接形式，在里更新
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2