NYOJ 万里挑一

NYOJ 万里挑一

万里挑一

描述

有两个大小为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<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#define MAX 100005
using namespace std;
int A[MAX],B[MAX];
bool comp(const int &a,const int &b){return a>b;
}
struct cmp{bool operator()(const int &a,const int &b){//优先队列内元素由小到大排列 return a>b;}
};
int main(){int N,K;while(cin>>N>>K){priority_queue<int,vector<int>,cmp>pq;for(int i=0;i<N;i++){//cin>>A[i];scanf("%d",&A[i]);}for(int i=0;i<N;i++){//cin>>B[i];scanf("%d",&B[i]);}//程序主要思想 // 将A,B,数组由大到小排列，让A中最大的数从B中加K个数，得到的这K个数可能为 最大的K个数//然后再让A第二大的数从B中加数，若有一个小于A[i] +B[j]小于pq.top(),说明此时B中余下的数加A[i]都不会大于 pq.top(),break//若发现有大于pq.top()的数，入队 sort(A,A+N,comp),sort(B,B+N,comp);for(int i=0;i<K;i++){pq.push(A[0]+B[i]);}	for(int i=1;i<N;i++){for(int j=0;j<N;j++){int num=A[i]+B[j];if(num&p()){break;}else {pq.pop();pq.push(num);}}}while(K--){printf("%d ",pq.top());pq.pop();}}
}

sort ，与priority_queue 自定义comp的区别可以认为：

sort中按comp的中大小顺序排列数组即在comp中return a>b 则数组按由大到小排列

而priority_queue中

struct comp{
bool operator()(const int &a,const int &b){
//优先队列内元素由小到大排列 ，若由大到小排列则为<
return a>b;
}
};

与sort的comp相反