NC50940. Running Median

描述

输入描述

The first line of input contains a single integer , 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 , 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.

示例1

输入:

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 56

输出:

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

原站题解

#include<bits/stdc++.h>
using namespace std;
vector<int>ve,ans;
int main(){
	int p;scanf("%d",&p);
	while(p--){
		ve.clear();ans.clear();
		int q,m,k;scanf("%d%d",&q,&m);
		printf("%d %d\n",q,m/2+1);
		for(int i=1;i<=m;i++){
			scanf("%d",&k);
			ve.insert(upper_bound(ve.begin(),ve.end(),k),k);
			if(i&1) ans.push_back(ve[(i-1)/2]);
		}
		for(int i=0;i<ans.size();i++){
			printf("%d ",ans[i]); 
			if((i+1)%10==0&&i!=ans.size()-1) printf("\n");
		}
		printf("\n");
	}
	return 0;
}

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

int n;
vector<int> a;
int main()
{
	scanf("%d",&n);
	while(n--)
	{
		a.clear();
		int num,m;
		scanf("%d%d",&num,&m);
		printf("%d %d\n",num,(m+1)/2);
		for(int i=1;i<=m;++i)
		{
			int x;
			scanf("%d",&x);
			a.insert(upper_bound(a.begin(),a.end(),x),x);
			if(i%2)
				printf("%d ",a[(i-1)/2]);
			if(!(i%20))
				printf("\n");
		}
		printf("\n");
	}
	return 0;
}