《算法进阶指南》—0x05:Running Median(优先队列,堆排序★★☆)

Running Median

https://ac.nowcoder.com/acm/problem/50940

思路:

1:维护一个最大堆和一个最小堆,若元素数量为1,直接输出即可。否则首先先将前两个元素中较大的加入最小堆,较小的加入最大堆。
2:然后每次添加新元素的时候,先将其与最大堆和最小堆的堆顶进行对比,如果其大于最小堆堆顶则插入最小堆,如果其小于最大堆堆顶则插入最大堆,否则选择元素数量较小的一堆。
3: 每次插入结束后如果两堆的元素数量差大于1则从元素数量较多的一堆中取出堆顶插入另一堆,这样可以保证两堆元素数量始终是平衡的。 在这种情况下,选取中位数只需要选取元素数量多 1 的一堆的堆顶即可。
4:注意输出格式!

code:

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <string>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <algorithm>
#include <functional>
typedef long long ll;
using namespace std;
priority_queue<int, vector<int>, greater<int>> mx;
priority_queue<int, vector<int>, less<int>> mi;
void clear(priority_queue<int, vector<int>, less<int>>& mi)
{
    priority_queue<int, vector<int>, less<int>> empty;
    swap(empty, mi);
}
void clear(priority_queue<int, vector<int>, greater<int>>& mi)
{
    priority_queue<int, vector<int>, greater<int>> empty;
    swap(empty, mi);
}
ll read()
{
    ll s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int p, m, t;
    p = read();
    while (p--)
    {
        ll sum = 1;
        t = read();
        m = read();
        int w;
        cout << t << " " << (m + 1) / 2 << endl;
        if (m == 1) {
            w = read();
            cout << w << endl;
            continue;
        }
        int t1, t2, t;
        t1 = read(); t2 = read();
        mx.push(max(t1, t2));
        mi.push(min(t1, t2));
        cout << t1 << " ";
        for (int i = 3; i <= m; i++)
        {
            w = read();

            if (w >= mx.top())
            {
                mx.push(w);
            }
            else if (w <= mi.top())
            {
                mi.push(w);
            }
            else if (mi.size() >= mx.size())
            {
                mi.push(w);
            }
            else
            {
                mx.push(w);
            }
            int kk = mx.size() - mi.size();
            while (abs(kk) >= 2)
            {

                if (mx.size() > mi.size())
                {
                    int temp = mx.top();
                    mx.pop();
                    mi.push(temp);
                }
                else if (mi.size() > mx.size())
                {
                    int temp = mi.top();
                    mi.pop();
                    mx.push(temp);
                }
                kk = mx.size() - mi.size();
            }

            if (i & 1)
            {
                sum++;
                if (mi.size() > mx.size())
                {
                    cout << mi.top() << " ";
                }
                else
                {
                    cout << mx.top() << " ";
                }
                if (sum % 10 == 0)
                {
                    cout << endl;
                }
            }
        }
        if (sum % 10)
        {
            cout << endl;
        }
        sum = 0;
        clear(mi);
        clear(mx);
    }
    return 0;
}
算法竞赛进阶指南 文章被收录于专栏

1

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
1 1 评论
分享

全站热榜

正在热议