题解 P1631 【序列合并】

~~**各位，我发现有一种新奇的做法就能解决此题~**~~ # 39行实测AC代码+思路 ## 先讲思路。 - 很显然我们有 _a和b两个数组_ 。 - 很显然我们要用一个 _c数组存和_ 。 - 很显然要用heap堆排(**实际上是只用了向下维护操作**)。 - 我们的c[ i ][ j ]，用来存储**a中第i个数分别和b中的所有数相加得到的结果**。很显然 会 爆空间，所以等下会有优化。 ```cpp for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) c[i][j] = a[i]+b[j];//a中第i个数分别和b中的所有数相加得到的结果 ``` - 依题意得：a是有序数列，b也是有序数列，则对于任意c[ i ]也会是一个有序数列。 - 那么我们就把c[ i ]的第一个数存入heap。 ```cpp for (int i = 1;i <= n;i++) heap[i] = c[i][j]; ``` - 然后维护一下heap - while（没有输出够n个数） - { - 输出； - 放入 **堆顶数所在的数组的下一个数**（好好咀嚼一下） - 维护 - } ### 优化 - 经过arfa同志的提醒，我们发现定义的c数组会爆空间。 - 于是我们开始了优化之旅。 - 首先我们知道，heap[ i ]只需要用一个值，那我们可不可以在heap需要的时候再把c[ i ][ j ]算出来呢？ - 然后我们发现 c[ i ][ j ] = a[ i ]+b[ j ]中i相当于目前对顶数所在的数组，j就表示下一个数的下标。 - 于是优化就出来了。 ```cpp for (int i = 1;i <= n;i++) heap[i] = a[i]+b[1] …… int t = from[1]; step[t]++; heap[1]=a[t] + b[ step[t] ]; ``` - 有人可能看不懂。我做一个比喻吧。假如你是拱野驾校隔壁的老王肠粉店店长，因为拱野驾校的学员很多，所以你的生意很红火。但是他们想要各种口味的。你想了一个办法：买来几个碟子，先把各种肠粉都做几份，再卖出去。实际上，你只需要现做现卖的合成就~~ojbk~~了。 ## 上代码 ```cpp #include<bits/stdc++.h> using namespace std; int a[100000],b[100000],heap[100000],from[100000],step[100000],n,sum=1; void swap(int x,int y)//手打swap交换，同时交换来源数组。 { int k = heap[x]; heap[x] = heap[y]; heap[y] = k; k = from[x]; from[x] = from[y]; from[y] = k; } 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]); for (int i = 1;i <= n;i++) heap[i] = a[i]+b[1],from[i] = i,step[i] = 1; //这一步就是优化。把c去掉了，取而代之的是现做现卖的合成。 while (sum <= n) { printf("%d ",heap[1]); int t = from[1]; step[t]++; heap[1]=a[t] + b[ step[t] ];//现做现卖的合成。 int x = 1,s; while (x<<1 <= n)//经典的下传 { s = x<<1; if (heap[s] > heap[s + 1] && s + 1 <= n) s++; if (heap[x] > heap[s]) { swap(x,s); x = s; }else break; } sum++; } return 0; } ```