小跟堆和大跟堆的操作-蒲公英云

小跟堆和大跟堆的操作

小咪咪 2022-09-07 03:47 255阅读 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;
}