Description
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.
Input
The first line of input contains a single integer 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), 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.
Output
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.
Sample Input
3 1 9 1 2 3 4 5 6 7 8 9 2 9 9 8 7 6 5 4 3 2 1 3 23 23 41 13 22 -3 24 -31 -11 -8 -7 3 5 103 211 -311 -45 -67 -73 -81 -99 -33 24 56Sample Output
1 5 1 2 3 4 5 2 5 9 8 7 6 5 3 12 23 23 22 22 13 3 5 5 3 -3 -7 -3随着蓝书来到这题，对顶堆算法动态维护中位数。大根堆存1~m 位置的数，小根堆 m+1~n，小根堆堆顶就是中位数。
添加元素时，小于小根堆堆顶的进大根堆，大于的进小根堆，并且每次添加完后不能改变上述性质
#include<iostream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #include<deque> #include<set> #include<bitset> #include<cctype> #define LL long long #define maxn (LL)1e5 #define INF 0x3f3f3f3f const double eps = 0.00001; using namespace std; priority_queue<int> Q1;//大根堆 1~n/2 priority_queue<int,vector<int>,greater<int> > Q2;//小根堆 n/2+1 int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); #endif // ONLINE_JUDGE int n,m; int T; cin>>T; for(int k = 1;k<=T;++k) { while(!Q1.empty()) Q1.pop();//注意清空 while(!Q2.empty()) Q2.pop(); cin>>n>>m; cout<<k<<" "; vector<int> v; for(int i= 1;i<=m;++i) { int a; cin>>a; if(Q2.size()==0) {Q2.push(a); v.push_back(a); continue; } if(a>Q2.top()) Q2.push(a); else Q1.push(a); if(Q1.size()>Q2.size()) {//以下维护性质 a = Q1.top(); Q1.pop(); Q2.push(a); } if(i%2==0&&Q1.size()<Q2.size()){ a = Q2.top(); Q2.pop(); Q1.push(a); } if(i&1) v.push_back(Q2.top());//奇数'取出' } cout<<v.size()<<endl; for(int l = 0;l<v.size();l++) { cout<<v[l]<<" "; if((l+1)==0) cout<<endl; } cout<<endl; } }
