POJ - 3784 Running Median(动态维护中位数)

题目链接：点击查看

题目大意：给出n个数，依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数

题目分析：动态维护中位数，我们可以直接用两个二叉堆来维护，一个是小顶堆，一个是大顶堆，让大顶堆在中位数左侧，让小顶堆在中位数右侧，两个二叉堆堆顶相接拼起来，因为每次需要询问的是奇数时候的中位数，所以每次的中位数一定是确定的，这个时候我们可以将当前中位数保存在大顶堆的堆顶或小顶堆的堆顶，都是一样的，我们以小顶堆堆顶为中位数为例，每次维护的时候，若新插入的数比小顶堆的堆顶要大，就插入到小顶堆中，反之插入到大顶堆中，然后根据中位数的性质，即当整个数列为奇数时，中位数左右两侧的元素个数相等，依次作为依据实时维护两个二叉堆即可

因为优先队列就是基于大顶堆实现的，我们重载一下运算符就变成小顶堆了，可以直接使用

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int kase,n;scanf("%d%d",&kase,&n);vector<int>ans;priority_queue<int,vector<int>,less<int> >L;//大顶堆priority_queue<int,vector<int>,greater<int> >R;//小顶堆for(int i=1;i<=n;i++){int num;scanf("%d",&num);if(R.empty()||num>R.top())R.push(num);elseL.push(num);if(i&1){while(L.size()>R.size()-1){R.push(L.top());L.pop();}while(L.size()<R.size()-1){L.push(R.top());R.pop();}ans.push_back(R.top());}}printf("%d %d\n",kase,ans.size());for(int i=0;i<ans.size();i++)//注意输出格式{if(i){if(i%10)putchar(' ');elseputchar('\n');}printf("%d",ans[i]);if(i==ans.size()-1)putchar('\n');}}return 0; }

 

总结

以上是生活随笔为你收集整理的POJ - 3784 Running Median(动态维护中位数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。