(Description)
有两个长度都是(N)的序列(A)和(B)，在(A)和(B)中各取一个数相加可以得到(N^2)个和，求这(N^2)个和中最小的(N)个。
(Input)
第一行一个正整数(N)；
第二行(N)个整数(A_i) 满足(A_i≤A_{i+1})且(A_i≤10^9);
第三行(N)个整数(B_i)满足(B_i≤B_{i+1})且(B_i≤10^9);
【数据规模】
对于(50%)的数据中，满足(1<=N<=1000)；
对于(100%)的数据中，满足(1<=N<=100000)。
(Output)
输出仅一行，包含(N)个整数，从小到大输出这(N)个最小的和，相邻数字之间用空格隔开。
(Solution1)
使用堆来解决，但我们想到，如果把(N^2)个和全部统计，那么显然时间复杂度是无法承受的
因为序列是有序的，所以很明显有这样一个性质(:A[i]+B[j]<=A[i]+B[j+1])，所以说我们的两层for循环第一层是(B)数组，第二层的(A)数组从(A)数组的最小值也就是(A[1])开始就行了，这样等效于遍历全部的(A[i],B[i])，只不过除去无用的答案就是了，这一切可以用STL堆来实现。
所以我们建一个数组，(to[i])表示(b)的第(i)项当前所对的(A)数组的值，一开始让他们全部指向(A[1])，然后在从堆中取数的过程中将“指针”向上一格再放进去就OK了，复杂度(O(nlogn))
Code1
#include<cstdio>
#include<queue>
using namespace std;
int a[100005]={}, b[100005]={}, to[100005]={},i, n;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
int main()
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i = 1; i <= n; i++)
{
scanf("%d", &b[i]); to[i] = 1;
q.push(pair<int, int>(a[1] + b[i], i));
}
while (n--)
{
printf("%d ", q.top().first);
i = q.top().second; q.pop();
q.push(pair<int, int>(a[++to[i]] + b[i], i));
}
return 0;
}
(Solution2)
这里是另一个非堆的做法，考虑令(L=a[1]+b[1],R=a[n]+b[n])，然后二分第(n+1)小的值即可，最后得出第n大的值，然后通过枚举加剪枝过
具体细节有很多优化，来看看代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[100007],b[100007],answer[1000007];int n;//注意answer要开大，因为可能有重复
bool judge(int x)
{
int sum=0;
for(int i=1;i<=n;++i)
{
if(sum>n||a[i]+b[1]>x)break;//当a[i]+b[1]>x时就不用再做任何枚举了，因为后面的值一定是大于这个值的
for(int j=1;j<=n;++j)
{
if(a[i]+b[j]<x)
{
++sum;
if(sum>n)break;//找够了立即退出
}
if(a[i]+b[j]>x)break;//因为b[j]单调，所以如果>x后面的b就不用继续枚举了
}
}
if(sum>=n)return 1;
else return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=n;++i)
cin>>b[i];
int l=a[1]+b[1],r=a[n]+b[n];
while(l!=r)//二分模板
{
int mid=(l+r)/2;
if(judge(mid)==1)
r=mid;
else l=mid+1;
}
--l;//注意--l
int s=0;
for(int i=1;i<=n;++i)//最后的枚举技巧和上面差不多
{
if(a[i]+b[1]>l)break;//注意超了就不用枚举了
for(int j=1;j<=n;++j)
{
if(a[i]+b[j]<=l)
{
++s;
answer[s]=a[i]+b[j];
}
else break;
}
}
sort(answer+1,answer+s+1);
for(int i=1;i<=n;++i)
cout<<answer[i]<<" ";
return 0;
}