小跟堆和大跟堆的操作

小咪咪 2022-09-07 03:47 158阅读 0赞

头文件： include < queue>

修改一个节点，保持原来的顺序，时间复杂度：  O ( l o g n ) O(logn) O(logn)

默认是大跟堆，大跟堆有两种操作：  
（1）

priority_queue<ll, vector<ll>, less<ll> >a; 
    // 注意最后的空格

（2）大跟堆其实不用那么麻烦，直接：

priority_queue<ll> a, b;

小跟堆:

priority_queue<ll, vector<ll>, greater<ll> >a, b;

--------------------

一个例题

// Problem: 对象存储调度问题
    // Contest: HDOJ
    // URL: https://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&cid=1029
    // Memory Limit: 524 MB
    // Time Limit: 4000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<queue>
    using namespace std;
    
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    typedef long long ll;
    
    int n, m;
    ll t;
    
    void solve()
    { 
    	cin >> n >> m;
    	priority_queue<ll, vector<ll>, less<ll> >a, b;
    	rep(i,1,n)
    	{ 
    		cin >> t;
    		a.push(t);
    	} 
    	rep(i,1,m){ 
    		cin >> t;
    		b.push(t);
    	}
    	bool f = true;
    	while(a.size() && f)
    	{ 
    		ll x = a.top();
    		a.pop();
    		while(b.size() && f)
    		{ 
    			ll y = b.top();
    			b.pop();
    			if(y-x>=0){ 
    				b.push(y-x);
    				break;
    			}
    			else{ 
    				f = false;
    				break;
    			}
    		}
    	}
    	if(f) puts("Yes");
    	else puts("No");
    }
    
    
    int main()
    { 
    
    	ios::sync_with_stdio(false);cin.tie(0);
    	int Case;cin >> Case;
    	while(Case--)
    		solve();
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java 中的大根堆和小根堆

小根堆和大根堆 **[完全二叉树][Link 1]**：完全二叉树是效率很高的数据结构，完全二叉树是由[满二叉树][Link 2]而引出来的。对于深度为K的，有n个结...

ゝ一纸荒年。/ 2024年04月17日 23:34/ 0 赞/ 77 阅读

相关【软考】数据结构 - 堆结构（小顶堆、大顶堆和二叉堆）

一、堆是什么？堆结构是一种具有特殊性质的基于完全二叉树的树形数据结构堆是一个完全二叉树，即除了最后一层，其他层的节点都是满的最后一层的节点都是从

红太狼/ 2024年03月24日 15:06/ 0 赞/ 80 阅读

相关堆（Heap）大根堆、小根堆

堆（Heap）大根堆、小根堆文章目录堆（Heap）大根堆、小根堆 Heap是一种数据结构堆的存储堆的操作：insert 堆的操

ゝ一纸荒年。/ 2022年11月08日 11:49/ 0 赞/ 190 阅读

相关小跟堆和大跟堆的操作

头文件： include < queue> 修改一个节点，保持原来的顺序，时间复杂度： O ( l o g n ) O(logn) O(logn) 默认是大跟堆，大跟堆有

小咪咪/ 2022年09月07日 03:47/ 0 赞/ 159 阅读

相关最大堆，最小堆插入/删除以及最大堆的排序

先说一下最大堆如何排序：转自：http://www.cnblogs.com/luchen927/archive/2012/03/08/2381446.html 最大堆和最小堆

约定不等于承诺〃/ 2022年07月31日 16:15/ 0 赞/ 278 阅读

相关【算法】堆排序大根堆和小根堆建堆以及元素输出

这样一组数 45 28 49 16 37 82 56 75初始堆后,利用堆排序怎么排,规律是什么? 首先建立完全二叉树 45 28 49 16 37 82 56

r囧r小猫/ 2022年07月13日 00:52/ 0 赞/ 262 阅读

相关大根堆和小根堆

大根堆和小根堆在排序和选择第K大的数中经常有用到。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

川长思鸟来/ 2022年02月27日 13:12/ 0 赞/ 325 阅读

相关 python实现最大堆，最小堆和堆排序

目录 0.什么是堆 1.最大堆的实现 2.最小堆的实现 3.堆排序 0.什么是堆小堆和大堆分为如下图： ![2018091712014232][] > 堆

电玩女神/ 2022年02月20日 14:17/ 0 赞/ 512 阅读

相关堆排序最大堆最小堆

package com.tree; import java.text.SimpleDateFormat; import java.util.Arrays

￡神魔★判官ぃ/ 2021年10月15日 02:49/ 0 赞/ 386 阅读

相关堆排序（大顶堆、小顶堆）----C语言

堆排序之前的随笔写了栈（[顺序栈][Link 1]、[链式栈][Link 2]）、队列（[循环队列][Link 3]、[链式队列][Link 4]）、[链表][Link

小鱼儿/ 2021年06月10日 20:38/ 0 赞/ 511 阅读