描述: 有两个长度为N的序列 AB,从AB中各选一个数,可以得到N^2个和,求这N^2个和中最小的N个 输入 5 1 3 2 4 5 6 3 4 1 7 输出 2 3 4 4 5
分析:
首先限定输出n个数,入堆n个数,输出n个数,
#include<iostream> #include<queue> #include<algorithm> using namespace std; const int maxn=100000; int n,i,j; int a[100000]; int b[100000]; typedef struct node{ int sum; int b; bool operator >(const node &a)const{ return sum>a.sum; } }node; void merge(){ sort(a,a+n); sort(b,b+n); priority_queue<node,vector<node>,greater<node> >q;//注意最后两个 > 符号的位置 for(i=0;i<n;i++){ node tmp; tmp.sum=a[i]+b[0]; tmp.b=0; q.push(tmp); } for(i=0;i<n;i++){//输出n个数 node tmp; tmp=q.top(); q.pop(); cout<<tmp.sum<<" "; tmp.sum=tmp.sum-b[tmp.b]+b[tmp.b+1]; tmp.b++; q.push(tmp); } return ; } int main() { // int n; int i,j; cin>>n; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++) cin>>b[i]; merge(); }