题解 P1631 【序列合并】
二分答案 把答案在这N^2个数中逐排比较 遇到大于答案的或符合条件的数超了就break 最后选出小于答案的sort一下输出前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;
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;}}
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;
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;
}