[TJOI2010] 中位数

题目描述

给定一个由 $N$ 个元素组成的整数序列，现在有两种操作：

• $\texttt{1 add }\textit{a}$：在该序列的最后添加一个整数 $a$，组成长度为 $N + 1$ 的整数序列。
• $\texttt{2 mid}$：输出当前序列的中位数。

中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）

例 $1$：$[1, 2, 13, 14, 15, 16]$ 中位数为 $13$。 例 $2$：$[1, 3, 5, 7, 10, 11, 17]$ 中位数为 $7$。 例 $3$：$[1, 1, 1, 2, 3]$ 中位数为 $1$。

输入格式

第一行为初始序列长度 $N$。第二行为 $N$ 个整数，表示整数序列，数字之间用空格分隔。第三行为操作数 $M$，即要进行 $M$ 次操作。下面为 $M$ 行，每行输入格式如题意所述。

输出格式

对于每个 $\verb!mid!$ 操作输出中位数的值。

样例 #1

样例输入 #1

6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid

样例输出 #1

5
13

提示

数据范围及约定

• 对于 $30\%$ 的数据，$1 ≤ N ≤ 10,000$，$0 ≤ M ≤ 1,000$。
• 对于 $100\%$ 的数据，$1 ≤ N ≤ 100,000$，$0 ≤ M ≤ 10,000$。

序列中整数的绝对值不超过 $10^9$，序列中的数可能有重复。

动态数组vector，sort 超时做法

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> v;
int a[100010];
char s[5];
int main(void){
	int n,m,x,l;
	scanf("%d",&n);
	v.clear();
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) v.push_back(a[i]); 
	scanf("%d",&m); 
	while(m--){
		scanf("%s",s);
		if(s[0]=='a'){
			scanf("%d",&x);
			v.push_back(x); 
		}else{
			sort(v.begin(),v.end());
			l=v.size();
			if(l%2==0) cout<<v[l/2-1]<<endl;
			else cout<<v[l/2]<<endl;
		}
	}
	return 0;
}

优化解法

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;

priority_queue<int,vector<int>,greater<int> > p;//小根堆 
priority_queue<int,vector<int>,less<int> > q;//大根堆 
int main(void){
	int n,mid,m;//mid记录中位数
	cin>>n>>mid;
	for(int i=1;i<n;i++){//输入的第二行的第一个数字已经输入了(mid)
		int t;
		cin>>t;
		if(t>mid) p.push(t);//如果后续的数字大于原先的中位数，就存入小根堆中
		else q.push(t);
		if(p.size()<q.size()){//若小根堆的长度比大根堆的小，则证明中位数是大根堆的第一个元素
			p.push(mid);
			mid=q.top();
			q.pop(); 
		}else if(p.size()>q.size()+1){
			q.push(mid);
			mid=p.top();
			p.pop(); 
		}
	}
	cin>>m;
	while(m--){
		string s;
		cin>>s;
		if(s[0]=='a'){
			int t;
			cin>>t;
			if(t>mid) p.push(t);
			else q.push(t);
			if(p.size()<q.size()){
				p.push(mid);
				mid=q.top();
				q.pop(); 
			}else if(p.size()>q.size()+1){
				q.push(mid);
				mid=p.top();
				p.pop(); 
			}
		}else{
			cout<<mid<<endl;
		}
	}
	return 0;
}

n个最小和

题目描述

给出两个包含 n 个整数的数组 A，B。 分别在 A, B 中任意出一个数并且相加，可以得到 n*n 个和。 求这些和中最小的 n 个。

输入格式

输入第一行一个整数 n(1≤n≤50000)。

接下来一行输入数组 A，用空格隔开。

接下来一行输入数组 B，用空格隔开。

1≤Ai,Bi≤10^9

输出格式

从小到大输出最小的 n 个和，用空格隔开。

输出时每行末尾的多余空格，不影响答案正确性

样例 #1

样例输入 #1

4
1 3 5 7
2 4 6 8

样例输出 #1

3 5 5 7

样例输入 #2

12
10 7 1 7 9 8 10 6 5 7 7 6 
6 6 6 1 3 6 5 9 3 7 9 3

样例输出 #2

2 4 4 4 6 6 7 7 7 7 7 7

暴力 58分

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=50010;

int a[N],b[N],t[N];
int main(void){
	freopen("nsum.in","r",stdin);
	freopen("nsum.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	int id=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			t[id]=a[i]+b[j];
			id++;
		}
	}
	sort(t+1,t+n*n);
	for(int i=1;i<=n;i++) cout<<t[i]<<" ";
	return 0;
}

优化解法：对A,B两个数组进行排序，先从小的数字开始加

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct node{
	int sum;
	int ai,bi;//记录两个数组的下表
	bool operator<(const node &r)const{
		return sum>r.sum;
	} 
};
int a[500005],b[500005];
int main(void){
	int n;
	priority_queue<node,vector<node>,less<node> > p;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) scanf("%d",&b[i]);
	sort(a,a+n);
	sort(b,b+n);
	for(int i=0;i<n;i++) p.push({a[i]+b[0],i,0}); 
	for(int i=0;i<n;i++){
		cout<<p.top().sum<<" ";
		node t=p.top();
		p.push({a[t.ai]+b[t.bi+1],t.ai,t.bi+1});
		p.pop(); 
	}
	return 0;
}