问题描述：

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

输入格式

输入第一行一个整数 $n(1\le n\le 50000)$。

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

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

$1\le A_i,B_i\le 10^9$

输出格式

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

样例输入

4 1 3 5 7 2 4 6 8

样例输出

3 5 5 7

代码解析：

// // main.cpp // ngezuixiaohe // // Created by apple on 2018/3/15. // Copyright © 2018年 apple. All rights reserved. // //优先队列 #include <iostream> #include <queue> #include <algorithm> using namespace std; /*用于最小值在前*/ struct Item{ int sum,index; Item(int a,int b):sum(a),index(b){} bool operator < (const Item &rhs)const{ return sum > rhs.sum; } }; int main() { int A[50005];int B[50005]; int n;//n个数 priority_queue<Item> q;//优先队列 //赋初始值 cin>>n; for(int i=0;i<n;i++){ cin>>A[i]; } for(int i=0;i<n;i++){ cin>>B[i]; } //排序a,b sort(A,A+n); sort(B,B+n); //先向队列中放入n个数。 for(int i=0;i<n;i++){ Item it(A[i]+B[0],0); q.push(it); } //output for(int i=0;i<n;i++){ Item item=q.top(); q.pop(); cout<<item.sum; if(i!=n-1)cout<<" "; int b=item.index; if(b+1<n){ Item ans(item.sum-B[b]+B[b+1],b+1); q.push(ans); } } return 0; } -----

其他解法：

【题意】有两个长度为 N 的序列 A 和 B ，在 A 和 B 中各任取一个数可以得到 N2 个和，求这 N2 个和中最小的 N 个。

【数据范围】 Ai,Bi≤109，N≤105

【思路1】30分做法  直接把 N2 个和都算出来，排序，然后输出前N个。  时间复杂度： O(n2logn)   空间复杂度： O(n2)

【思路2】AC做法  求前N小，涉及到单调性，试着排序使得A，B两个序列从小到大。

我们从1到N依次找到前N小的和，那么每次就要从决策中选出一个最小的元素，现在要求每次决策考虑的元素个数尽可能少。

可以按行把所有的 N2 个和分成 N 类：  第1行： A1+B1<A1+B2<A1+Bi<...<A1+Bn   第2行： A2+B1<A2+B2<A2+Bi<...<A2+Bn   ......   第i行： Ai+B1<Ai+B2<Ai+Bi<...<Ai+Bn   ......   第n行： An+B1<An+B2<An+Bi<...<An+Bn

对于第i行，若 j<k ，则必然先选 Ai+Bj ，后选 Ai+Bk 。  那么，在决策的时候只用考虑每一行当前未选的最前一个。

即：设l evel[i] 表示当前第i行的 (Ai+Blevel[i]) 在决策中，每次选取s，满足最小化 (Ai+Blevel[i]) ，然后把 (As+Blevel[s]) 最为当前最小，再 inc(level[s]) 。  至于每次的决策，用堆可以做到 O(logn) 完成。

时间复杂度： O(nlogn)   空间复杂度： O(n)

代码：实测136ms

#include <cstdio> #include <cctype> #include <queue> #include <algorithm> using namespace std; const int N=161240; int n; int A[N],B[N]; int lev[N]; inline int Read(void) { int s=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) s=s*10+c-'0'; return s; } struct cmp { inline int operator () (int i,int j) { return A[i]+B[lev[i]]>A[j]+B[lev[j]]; } }; priority_queue<int,vector<int>,cmp> q; int main(void) { n=Read(); for (int i=1;i<=n;i++) A[i]=Read(); for (int i=1;i<=n;i++) B[i]=Read(); sort(A+1,A+n+1); sort(B+1,B+n+1); fill(lev+1,lev+n+1,1); for (int i=1;i<=n;i++) q.push(i); int now; for (int i=1;i<=n;i++) { now=q.top(),q.pop(); printf("%d ",A[now]+B[lev[now]++]); q.push(now); } printf("\n"); return 0; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

【思路3】AC做法  首先排序，然后还是用【思路2】的思路，从1到N依次求前N小。

注意到【思路2】中我们只使用了横向的分类，而没有考虑纵向的分类，这是可以有一些决策状态排除掉的。  于是我们想到直接把这些状态当作一个二维的图来看：

B\A 1 2 … i … n 1             2             …             i             …             n            

其中 (i,j) 这个格子表示 Ai+Bj 。

我们变为了二维的扩展，即在当前状态中选择一个最小的，然后向下、向右扩展决策状态。  这里需要注意的是，有些格子是不用加入待决策状态中的：它的左边或上边还没有决策出来。  这样有一定的优化作用。

时间复杂度： O(nlogn)   空间复杂度： O(n)

代码：实测88ms

#include <cstdio> #include <cctype> #include <queue> #include <algorithm> using namespace std; #define mp(i,j) make_pair(i,j) #define fs first #define sc second typedef pair<int,int> PairInt; const int N=161240; int n; int A[N],B[N]; int cross[N],line[N]; inline int Read(void) { int s=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) s=s*10+c-'0'; return s; } struct cmp { inline int operator () (PairInt Pi,PairInt Pj) { return A[Pi.fs]+B[Pi.sc]>A[Pj.fs]+B[Pj.sc]; } }; priority_queue<PairInt,vector<PairInt>,cmp> q; inline int Check(int i,int j) { if (cross[i]+1<j) return 0; if (line[j]+1<i) return 0; return 1; } int main(void) { n=Read(); for (int i=1;i<=n;i++) A[i]=Read(); for (int i=1;i<=n;i++) B[i]=Read(); sort(A+1,A+n+1); sort(B+1,B+n+1); PairInt now; q.push(mp(1,1)); for (int i=1;i<=n;i++) { now=q.top(),q.pop(); printf("%d ",A[now.fs]+B[now.sc]); cross[now.fs]=now.sc; line[now.sc]=now.fs; if (Check(now.fs+1,now.sc)) q.push(mp(now.fs+1,now.sc)); if (Check(now.fs,now.sc+1)) q.push(mp(now.fs,now.sc+1)); } printf("\n"); return 0; } 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162

【思路4】AC做法  按照【思路1】，我们把所有可能的情况都算出来，然后排序。  然而【思路1】的时间和空间都是我们承受不了的，怎么办？  想办法把一些一定不可能的状态给消除掉。

首先还是给A，B排序，同样还是这个表：

B\A 1 2 … i … n 1             2             …             i             …             n            

观察到，对于 (i,j) 这个点，比它小的元素至少有 i×j−1 个。  由于我们要求前N小的，所以满足要求的点至少要满足 i×j−1<n 即 i×j≤n 。  这样我们可以把点的个数缩小至 

⌊n1⌋+⌊n2⌋+...+⌊ni⌋+...+⌊nn⌋=O(n∑i=1n1i)=O(nlogn)

时间复杂度： O(nlog2n)   空间复杂度： O(nlogn)

代码：实测172ms

#include <cstdio> #include <cctype> #include <algorithm> using namespace std; const int N=161240; const int S=3000000; int n; int A[N],B[N]; int t[S],len; inline int Read(void) { int s=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) s=s*10+c-'0'; return s; } int main(void) { n=Read(); for (int i=1;i<=n;i++) A[i]=Read(); for (int i=1;i<=n;i++) B[i]=Read(); sort(A+1,A+n+1); sort(B+1,B+n+1); for (int i=1;i<=n;i++) for (int j=1;i*j<=n;j++) t[++len]=A[i]+B[j]; sort(t+1,t+len+1); for (int i=1;i<=n;i++) printf("%d ",t[i]); printf("\n"); return 0; } 12345678910111213141516171819202122232425262728293031323334

【小结】

对于无序的集合，通常要将它定序，常见的定序方法就是从小到大或者从大到小。

求第K小的方法通常有以下几种：  ①依次求  ②排序可能情况  ③二分答案

对于方法①“依次求”，每次在待定状态内的元素要尽可能少，可以通过某些性质来减少元素的个数。  通常的做法是构建多条元素的单调序列，满足先选完前一个再选后一个，这样用优先队列甚至不用（例如《丑数》一题）即可。  这种做法甚至可以扩展到二维单调性，然后在平面上扩展。

对于方法②“排序可能情况”，待定情况要尽可能的少，这要通过某些性质来排除一些不可能的情况。  例如本题只限定在 i×j≤n 内求，最后弄出了调和级数，总共的情况数为 O(nlogn) 。

对于方法③，在【变式】会提及。

方法的比较  方法①，方法②处理范围较小，询问较多的问题；  方法③处理范围较大，询问较少的问题。