$$ 小根堆：堆中某个节点的值总是大于等于其父节点的值，即根元素是最小的 $$

$$ 大根堆：堆中某个节点的值总是小于等于其父节点的值，即根元素是最大的 $$

例题

A.合并果子

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int tree[N] ,len;

void put(int x)
{
    tree[++ len] = x;
    int son = len;
    while (son > 1)
    {
        int fa = son / 2;
        if (tree[fa] <= tree[son]) return; // 已经维护完成，直接返回主函数
        swap(tree[fa] , tree[son]);
        son = fa;
    }
}

int get()
{
    int res = tree[1];
    tree[1] = tree[len --];
    int fa = 1;
    while (fa * 2 <= len)
    {
        int son = fa * 2;
        if (son + 1 <= len && tree[son + 1] < tree[son])
            son ++;
        if (tree[fa] <= tree[son]) break; // 已经满足二叉堆的性质，直接结束，返回res的值
        swap(tree[fa] , tree[son]);
        fa = son;
    }
    return res;
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        put(a);
    }

    int res = 0;
    for (int i = 1; i < n; i++) // 合并 n - 1 次
    {
        int x = get(),y = get();
        res += x + y;
        put(x + y);
    }

    cout << res;

    return 0;
}

B.序列合并

思路：贪心 +二叉堆

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n ,len;
int a[N] ,b[N];
struct Tree
{
    int x ,y;
    LL sum;
}tree[N];

void put(int x,int y)
{
    tree[++ len] = {x , y , 1ll * a[x] + 1ll * b[y]};
    int son = len;
    while (son > 1)
    {
        int fa = son / 2;
        if (tree[fa].sum <= tree[son].sum) return ;
        swap(tree[son] , tree[fa]);
        son = fa;
    }
}

void get()
{
    int x = tree[1].x,y = tree[1].y;
    cout << tree[1].sum << ' ';
    tree[1] = tree[len --];
    int fa = 1;
    while (fa * 2 <= len)
    {
        int son = fa * 2;
        if (son + 1 <= len && tree[son + 1].sum < tree[son].sum)
            son ++;
        if (tree[fa].sum <= tree[son].sum) break;
        swap(tree[fa] , tree[son]);
        fa = son;
    }
    put(x , y + 1); // 将这个数组的下一个元素放入堆中
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) put(i , 1); // 先把一个数组的第一个元素和第二个数组的所有元素之和入堆
    for (int i = 1; i <= n; i++) get();
    return 0;
}

D.工作安排

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

typedef long long LL;

const int N = 100010;

int n;
PII a[N];
int tree[N] ,len;

bool cmp(PII x,PII y)
{
    return x.first < y.first;
}

void put(int x)
{
    tree[++ len] = x;
    int son = len;
    while (son > 1)
    {
        int fa = son / 2;
        if (tree[fa] <= tree[son]) return ;
        swap(tree[fa] , tree[son]);
        son = fa;
    }
}

int get()
{
    int res = tree[1];
    tree[1] = tree[len --];
    int fa = 1;
    while (fa * 2 <= len)
    {
        int son = fa * 2;
        if (son + 1 <= len && tree[son + 1] < tree[son])
            son ++;
        if (tree[fa] <= tree[son]) break;
        swap(tree[fa] , tree[son]);
        fa = son;
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;

    sort(a + 1 , a + n + 1 , cmp); // 按照过期时间从小到大排序

    LL res = 0,now = 0,tot = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = a[i].first;
        put(a[i].second);
        now += a[i].second;
        tot ++;
        if (tot > t) // 如果时间不够的话，就把小根堆的根节点，也就是利润最低的任务踢出
        {
            now -= get();
            tot --;
        }
        res = max(res , now); // 有可能在踢的过程中取到最大
    }

    cout << res;

    return 0;
}

E.家庭作业

解题思路 ：和D题的相似，用大根堆来维护奶茶效果,如果满足不了条件，就拿最有用的奶茶使劲喝

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 200020;

int n ,len;
int nee;
double res;
PII now;
struct node
{
    int tea ,ne ,da;
}e[N] ,tree[N];

bool cmp(node x,node y)
{
    return x.da < y.da;
}

void put(int a,int b,int c)
{
    tree[++ len] = {a , b , c};
    int son = len;
    while (son > 1)
    {
        int fa = son / 2;
        if (tree[fa].tea >= tree[son].tea) return ;
        swap(tree[fa] , tree[son]);
        son  = fa;
    }
}

int get()
{
    if(tree[1].ne == 0)
    {
        tree[1] = tree[len --];
        int fa = 1;
        while (fa * 2 <= len)
        {
            int son = fa * 2;
            if (son + 1 <= len && tree[son + 1].tea > tree[son].tea) son ++;
            if (tree[fa].tea >= tree[son].tea) break;
            swap(tree[fa] , tree[son]);
            fa = son;
        }
    }
    return 1;
}

int main()
{
    scanf ("%d",&n);
    for (int i = 1; i <= n; i++)
        scanf ("%d %d %d",&e[i].tea,&e[i].ne,&e[i].da);

    sort(e + 1 , e + n + 1 , cmp);


    for (int i = 1; i <= n; i++)
    {
        int t = e[i].da;
        put(e[i].tea,e[i].ne,e[i].da);
        nee += e[i].ne;
        while (nee > t)
        {
            int k = get();
            if (tree[k].ne < (nee - t))
            {
                res += 1.0 * tree[k].ne / tree[k].tea;
                nee -= tree[k].ne;
                tree[k].ne = 0;
            }
            else
            {
                res += 1.0 * (nee - t) / tree[k].tea;
                tree[k].ne -= (nee - t);
                nee = t;
            }
        }
    }
    printf ("%.2lf",res);
    return 0;
}