P1631 序列合并 题解

# 朴素解法 直接把n^2个和都插入堆中，然后输出，复杂度为O(N^2logN)，本题数据N<100000,肯定过不了。 ``` #include<queue> #include<cctype> #include<cstdio> using namespace std; template<class T> inline void read(T &x) { x=0; int sign=1; char c; do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c)); do{ x=x*10+c-'0',c=getchar();}while(isdigit(c)); x*=sign; } int n,a[100001],b[100001]; int main() { read(n); for(register int i=1;i<=n;++i) read(a[i]); for(register int i=1;i<=n;++i) read(b[i]); priority_queue<int> q; for(register int i=1;i<=n;++i) for(register int j=1;j<=n;++j) q.push(-a[i]-b[j]); for(register int i=0;i<n;++i) { printf("%d ",-q.top()); q.pop(); } return 0; } ``` - 事实上，只要在朴素算法的代码上加一个小优化就行了。 - 两个长度为N的数列，和的总数为N^2，而答案只要输出其中最小的N个即可，那容易想到，在往堆中插入时就排除掉一些绝对不可能是答案的数。 - 假设此时要把 $a[i]+b[j]$ 插入堆，且$(i-1)*(j-1)>N$,那么这个数一定不会是最后的答案，因为对于$1<=s<i,1<=t<j$，可组成的和已经超过N个，且都要比$a[i]+b[j]$小。 ## AC代码 ``` #include<queue> #include<cctype> #include<cstdio> using namespace std; template<class T> inline void read(T &x) { x=0; int sign=1; char c; do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c)); do{ x=x*10+c-'0',c=getchar();}while(isdigit(c)); x*=sign; } int n,a[100001],b[100001]; int main() { read(n); for(register int i=1;i<=n;++i) read(a[i]); for(register int i=1;i<=n;++i) read(b[i]); priority_queue<int> q; for(register int i=1;i<=n;++i) for(register int j=1;(i-1)*(j-1)<=n&&j<=n;++j) //这里加一句就行了 q.push(-a[i]-b[j]); for(register int i=0;i<n;++i) { printf("%d ",-q.top()); q.pop(); } return 0; } ```