\(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; }

转载于:https://www.cnblogs.com/Liuz8848/p/10988914.html