NO.51十六届蓝桥杯备战|堆算法题|第k小|除2|最小函数值|序列合并|舞蹈课(C++)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n;
int heap[N];

void up(int child)
{
    int parent = child / 2;
    while (parent >= 1 && heap[child] < heap[parent])
    {
        swap(heap[child], heap[parent]);
        child = parent;
        parent = child / 2;
    }
}

void down(int parent)
{
    int child = parent * 2;
    while (child <= n)
    {
        if (child + 1 <= n && heap[child + 1] < heap[child]) child++;

        if (heap[child] >= heap[parent]) return;

        swap(heap[child], heap[parent]);
        parent = child;
        child = parent * 2;
    }
}

void push(int x)
{
    n++;
    heap[n] = x;
    up(n);
}

void pop()
{
    swap(heap[1], heap[n]);
    n--;
    down(1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t; cin >> t;
    while (t--)
    {
        int op; cin >> op;
        if (op == 1)
        {
            int x; cin >> x;
            push(x);
        }
        else if (op == 2)
        {
            cout << heap[1] << endl;
        }
        else
        {
            pop();
        }
    }
    
    return 0;
}

用堆维护数据流中的第k小

1. 创建一个大根堆
2. 维护大根堆的大小为k即可
   堆顶元素就是第k小

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
priority_queue<int> heap;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
        
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        heap.push(x);
        if (heap.size() > k) heap.pop();
    }
    while (m--)
    {
        int op; cin >> op;
        if (op == 1)
        {
            int x; cin >> x;
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }
        else if (op == 2)
        {
            if (heap.size() == k) cout << heap.top() << endl;
            else cout << -1 << endl;
        }
    }
    
    return 0;
}

每次挑选出，当前数组中最大的偶数，减小一半

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
priority_queue<LL> heap;

int n, k;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> k;
    LL sum = 0;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        sum += x;
        if (x % 2 == 0) heap.push(x);
    }
    while (heap.size() && k--)
    {
        int t = heap.top() / 2;
        heap.pop();
        
        sum -= t;
        if (t % 2 == 0) heap.push(t);
    }
    cout << sum << endl;
    
    return 0;
}

解法1：暴力求解
求出所有函数中的m个值，然后取前n个
解法2：利用堆+二次函数单调性
因为a和b都大于0，所以-b/2a一定小于0，对称轴在y轴左边，但是x取正整数，所以函数一定单调递增
仅需将x=1的所有函数值计算出来
然后每次拿出最小的那个，把对应的下一个函数值再计算出来
那么就可以用小根堆来实现这个过程

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e4 + 10;

int n, m;
LL a[N], b[N], c[N];

struct node
{
    LL f;
    LL num;
    LL x;

    bool operator < (const node& x) const
    {
        //小根堆，大元素下坠
        return f > x.f;
    }
};

priority_queue<node> heap;

LL calc(LL i, LL x)
{
    return a[i] * x * x + b[i] * x + c[i];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];        
    }

    for (int i = 1; i <= n; i++)
    {
        heap.push({calc(i, 1), i, 1});        
    }

    while (m--)
    {
        auto t = heap.top(); heap.pop();
        LL f = t.f, num = t.num, x = t.x;

        cout << f << " ";

        heap.push({calc(num, x + 1), num, x + 1});
    }
    
    return 0;
}

解法1：暴力求解
把所有的和全部算出来，然后找出最小的n个
解法2：利用单调性
先把a[i]+b[i]的所有值计算出来，放进小根堆中
然后拿出最小的值即堆顶元素，把下一个和再计算出来，再放入堆中
堆里面要存 和，a的编号，b的编号

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], b[N];

struct node
{
    int sum;
    int i, j;

    bool operator < (const node& x)const
    {
        return sum > x.sum;
    }
};

priority_queue<node> heap;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    //将ai+b1放进堆里面
    for (int i = 1; i <= n; i++)
    {
        heap.push({a[i] + b[1], i, 1});        
    }
    //依次拿出n个数
    for (int k = 1; k <= n; k++)
    {
        node t = heap.top(); heap.pop();
        int sum = t.sum, i = t.i, j = t.j;

        cout << sum << " ";
        if (j + 1 <= n) heap.push({a[i] + b[j + 1], i, j + 1});
    }
        
    return 0;
}

解法：利用小根堆，存所有相邻异性的差值，每次拿出最小的即可

1. 取出相邻的一对异性之后，他们的左右，有可能变成新的一对
   用双向链表存队列
2. 堆中，有可能存在已经出列的人
   bool st[N]sti表示i这个人是否已经出队
3. 堆中存什么
   技术差，左编号，右编号

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n;
int s[N]; //标记男女，0/1

int e[N];
int pre[N], ne[N];

struct node
{
    int d;
    int l, r;

    bool operator < (const node& x)const
    {
        if (d != x.d) return d > x.d;
        else if (l != x.l) return l > x.l;
        else return r > x.r;
    }
};

priority_queue<node> heap;
bool st[N]; //标记出队的人
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char ch; cin >> ch;
        if (ch == 'B') s[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> e[i];
        pre[i] = i - 1;
        ne[i] = i + 1;
    }
    pre[1] = ne[n] = 0;

    //把所有的差放进堆中
    for (int i = 2; i <= n; i++)
    {
        if (s[i] != s[i - 1])
        {
            heap.push({abs(e[i] - e[i - 1]), i - 1, i});
        }
    }

    //提取结果
    vector<node> ret; //暂存结果
    while (heap.size())
    {
        node t = heap.top(); heap.pop();
        int d = t.d, l = t.l, r = t.r;
        
        if (st[l] || st[r]) continue;

        ret.push_back(t);
        st[l] = st[r] = true; //标记l和r已经出列

        //修改指针，还原新的队列
        ne[pre[l]] = ne[r];
        pre[ne[r]] = pre[l];

        int left = pre[l], right = ne[r];
        if (left && right && s[left] != s[right])
        {
            heap.push({abs(e[left] - e[right]), left, right});
        }
    }

    cout << ret.size() << endl;
    for (auto& x : ret)
    {
        cout << x.l << " " << x.r << endl;        
    }
    
    return 0;
}