【蓝桥杯】n个最小和

题目

给出两个包含 $个整数的数组，。$

分别在 $, 中任意出一个数并且相加，可以得到个和。$

求这些和中最小的 $个。$

输入格式

输入第一行一个整数 $\le n \le 50000) </annotation> </semantics> </math>$

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

$\le A_i, B_i \le 10^9 </annotation> </semantics> </math>$

输出格式

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

样例输入

4

1 3 5 7

2 4 6 8

样例输出

3 5 5 7

题解

题解一

第一种比较容易想到的方法是：存下数组 a 的值，每输入一个数组 b 的值 t，将 t 和 a 数组每个值求和放进优先队列中，最后输出优先队列中前 n 个的值

但是内存要爆，无法 AC，原因是优先队列中要存 $n^2 </annotation> </semantics> </math>$

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
	int a[50000+5];
	priority_queue<int,vector<int>,greater<int> > sum;
	int n,t;
	int tmp;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++){
		cin>>t;
		for(int j=0;j<n;j++)
			sum.push( t + a[j] );
	}
	
	for(int i=0;i<n;i++){
		tmp = sum.top();
		sum.pop();
		if(i == 0)
			cout<<tmp;
		else
			cout<<" "<<tmp;
	}
	return 0;
}

题解二

优先队列中存 $n^2 </annotation> </semantics> </math>$

假设有两个升序的数组 A，B，那么一定有：

A $_1 </annotation> </semantics> </math>$
A $_2 </annotation> </semantics> </math>$
A $_3 </annotation> </semantics> </math>$
A $_n </annotation> </semantics> </math>$

此时，横向看随着 B 下标的增加，和值不断增大，竖向看随着 A 下标的增加，和值也不断增大

所以我们可以：

读取 A B 数组并排序
将 A[0] + B[0] 到 A[0] + B[n] 的和值加入优先队列中（此时优先队列中最小的值，肯定是所有和值里最小的）
开始出队，并入队和值的下一组，比如第一次出队的和值肯定是 A[0] + B[0]，那么我们入队 A[1] + B[0] （A[1] + B[0] 和 A[0] + B[1] 接近 A[0] + B[0]，而后者已经在优先队列中了）

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
struct node{
	int sum;
	int a;
	int b;
	bool operator<(const node &A)const{
		return sum > A.sum; 
	}
};
int main(){
	vector<int> a;
	vector<int> b;
	priority_queue<node> sum;
	int n,t;
	node tmp;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>t;
		a.push_back(t);
	}
	sort(a.begin(),a.end());
	for(int i=0;i<n;i++){
		cin>>t;
		b.push_back(t);
	}
	sort(b.begin(),b.end());
	for(int i=0;i<n;i++){
		tmp.a = 0;
		tmp.b = i;
		tmp.sum = a[tmp.a] + b[tmp.b];
		sum.push(tmp);
	}
	for(int i=0;i<n;i++){
		tmp = sum.top();
		sum.pop();
		if(i == 0)
			cout<<tmp.sum;
		else
			cout<<" "<<tmp.sum;
		tmp.a++;
		tmp.sum = a[tmp.a] + b[tmp.b];
		sum.push(tmp);
	}
	return 0;
}

返回目录，查看更多