欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Running Median 对顶堆 数据流中的中位数

程序员文章站 2022-03-31 20:02:42
...

链接:https://ac.nowcoder.com/acm/contest/1001/D
来源:牛客网

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.
输入描述:

The first line of input contains a single integer P(1≤P≤1000)P(1 \leq P \leq 1000)P(1≤P≤1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M(1≤M≤9999)M (1 \leq M \leq 9999)M(1≤M≤9999), giving the total number of signed integers to be processed. The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values.

输出描述:

For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.



开始一个空序列,每次往序列里插入一个数字,奇数次插入的时候打印序列中的中位数,
经典老题了
两个堆来维护,
Running Median 对顶堆 数据流中的中位数

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <stdlib.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \
	do { \
		cout << "\033[31;1m " << #x << " -> "; \
		err(x); \
	} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K, tot;


void PUSH(priority_queue<int>& lef, 
		priority_queue<int, vector<int>, greater<int> >& rig,
		int x) {
	tot ++;
	if(!rig.size() || x>rig.top()) 
		rig.push(x);
	else 
		lef.push(x);
	if(lef.size() > rig.size()+1) {
		rig.push(lef.top());
		lef.pop();
	}
	if(rig.size() > lef.size()+1) {
		lef.push(rig.top());
		rig.pop();
	}
}

#define QUERY (lef.size() > rig.size() ? lef.top() : rig.top())

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(Q);
	while(Q--) {
		read(m, n);
		printf("%d %d\n", m, n/2+1);
		priority_queue<int> lef;
		priority_queue<int, vector<int>, greater<int> > rig;

		int cnt = 0;
		for(int i=1, x; i<=n; i++) {
			read(x);
			tot = 0; //tot忘记清零 搞得内存超限
			PUSH(lef, rig, x);
			if(i & 1) {
				printf("%d", QUERY);
				++ cnt;
				if(cnt%10==0 || i==n) putchar('\n');
				else putchar(' ');
			}
//			printf("%d ", x);
		}
	}


#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}




相关标签: