解法1–优先队列
思路
如何在朴素做法$n^2$之上进行优化?我们每次都是要取出当前最小的两个数进行合并。由于原序列是有序的,$a[1]$是一定会被取到的。假设我们当前取出的是$a[i]+b[j]$,那么我们下一次取的就是$a[i]+b[j+1]$或$a[i+1]+b[j]$。我们先把$b$序列中所有数与$a[1]$的和放入优先队列,这样就满足了$a[i]+b[j+1]$的情况。(因为$a[1]$一定比$a$数组后面的小)
所以重点就是处理$a[i+1]+b[j]$,每次把取出$b[j]$对应的取到$a$数组中的位置往后移一个加入队列即可。
【注意】优先队列默认是大根堆。所以,要改成小根堆,用 greater
#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int n,a[N],b[N],to[N];
priority_queue<PII,vector<PII>,greater<PII> > q;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) {
scanf("%d",&b[i]);
q.push((PII){b[i]+a[1],i});
to[i]=1;
}
for(int i=1;i<=n;i++){
printf("%d ",q.top().first);
int j=q.top().second;
q.pop();
q.push((PII){b[j]+a[++to[j]],j});
}
return 0;
}
解法2–数学推断+枚举
思路
当 $i \cdot j > n$ 时,$A_i+B_j$ 一定不是前 n 小的数。
理由:因为两个序列均从小到大排列好了,所以如果 $x<=i$ 而且 $y<=j$ 那么 $A_x+B_y < A_i+B_j $ 。于是至少有 $i \cdot j$ 个数小于等于 $A_i+B_j$ 当 $i\cdot j>n$ 时,一定有多余 n 个数小于等于 $A_i+B_j$ ,所以 $A_i+B_j$ 一定不是前 n 小的数。
于是,我们可以枚举可能成为前 n 小的数的 $A_i+B_j$ ,然后排序输出~~
那么存放和的数组f要开多大?
我写了代码算了一下,$10^5$ 大概有 $1166750$,那么 f 数组就开 $2e6$ 。
代码:
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10,N2=2e6+10;
int n,cnt;
int d[N],e[N],f[N2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
for(int i=1;i<=n;i++) scanf("%d",&e[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i*j>n) break;
f[cnt++]=d[i]+e[j];
}
}
sort(f,f+cnt);
for(int i=0;i<n;i++){
printf("%d ",f[i]);
}
printf("\n");
return 0;
}
直接枚举 $i \cdot j <= n$ 的数
上面的做法是枚举所有值,当 $i \cdot j > n$ 就 break,这是比较好想的办法,当然还可以直接枚举所有 $ i \cdot j <= n$ 的数,其实这两种办法时间复杂度差不多,但是这种写法也有独到之处,需要练习一下。人人需要注意 sum 数组要开的足够大才行。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e5+10,N2=2e6;
int n,cnt;
int a[N],b[N],sum[N2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
int len=sqrt(n);
for(int i=1;i<=len;i++){ //i和j必然有一个小于等于根号n,就枚举这个数
for(int j=i;j<=n/i;j++){//行,j从i开始,到n/i,保证i*j<=n
sum[cnt++]=a[j]+b[i];
}
for(int j=i+1;j<=n/i;j++){//列,同理,要保证i*j<=n
sum[cnt++]=a[i]+b[j];
}
}
sort(sum,sum+cnt);
for(int i=0;i<n;i++){
printf("%d ",sum[i]);
}
printf("\n");
return 0;
}