nyoj 634 万里挑一

nyoj 634 万里挑一

万里挑一

描述

有两个大小为N的数组A和B，对于每一对（i, j）(0<=i,j<N)都可以得到一个数A[i]+B[j],这样就可以得到N*N个数了，你需要求出前K个大的数，easy?

输入

输入可能会有多组（小于十组），每组3行数据，第一行是两个整数N( N <= 100000 ) 和K(K<=N)，接下来2行，每行N个整数，每行的整数都用空格隔开

输出

每组一行，最大的K个数，用空格隔开，从小到大输出。

样例输入

4 3
1 2 3 4
3 6 5 4

样例输出

9 9 10

来源

郑大第六届校赛

 
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int a[100001],b[100001];
struct node {int v; int n;node(){}node(int a,int b):v(a),n(b){}  //不断更新新的队列bool operator < (const node& tmp ) const{return v< tmp.v;   //使队列维护从大到小的性质}
};
bool cmp(int aa,int bb)
{return aa > bb;
}
void fun(int *A,int *B,int *C,int n)
{priority_queue<node> q;int i;for( i = 0 ; i < n ; i++)q.push(node(A[i]+B[0],0));//先入队列n个数（第一个数是最大的）for( i = 0 ; i < n ; i++){node tmp = q.top(); q.pop(); //每次最大的数出队列，并保存到数组C中C[i] = tmp.v;            //也就是a中，重新赋值节约资源int b = tmp.n;            //初始值为0，表示最大数的下标if(b<n-1)             //保证下标数至少两个，{q.push(node(tmp.v - B[b] +B[b+1],b+1));//下标加1，表示第二大的数//tmp.v -B[b] + B[b+1] 是小于等于tmp.v的一个数入队列}}
}
int main()
{int k,i,n;while(scanf("%d%d",&n,&k)!=EOF){for(i = 0 ; i < n ; i++)scanf("%d",&a[i]);for(i = 0 ; i < n ;i++)scanf("%d",&b[i]);sort(a,a+n,cmp);   sort(b,b+n,cmp);  //将a,b都从小到大排列fun(a,b,a,k);printf("%d",a[k-1]);for(i = k -2 ;i>= 0 ;--i)printf(" %d",a[i]);printf("n");}}