韶关住房和城乡建设网站,一个微信可以做两个网站支付,网站建站推荐,网络推广网络营销【洛谷】 P1631 序列合并 题目描述 有两个长度为 N N N 的单调不降序列 A , B A,B A,B#xff0c;在 A , B A,B A,B 中各取一个数相加可以得到 N 2 N^2 N2 个和#xff0c;求这 N 2 N^2 N2 个和中最小的 N N N 个。 输入格式 第一行一个正整数 N N N#xff1b; 第二…【洛谷】 P1631 序列合并 题目描述 有两个长度为 N N N 的单调不降序列 A , B A,B A,B在 A , B A,B A,B 中各取一个数相加可以得到 N 2 N^2 N2 个和求这 N 2 N^2 N2 个和中最小的 N N N 个。 输入格式 第一行一个正整数 N N N 第二行 N N N 个整数 A 1 , A 2 , … , A N A_1,A_2,…,A_N A1,A2,…,AN。 第三行 N N N 个整数 B 1 , B 2 , … , B N B_1,B_2,…,B_N B1,B2,…,BN。 输出格式 一行 N N N 个整数从小到大表示这 N N N 个最小的和。 样例输入 #1 3 2 6 6 1 4 8 样例输出 #1 3 6 7 提示 对于 50 % 50\% 50% 的数据 N ≤ 1 0 3 N \le 10^3 N≤103。 对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1≤N≤105 1 ≤ a i , b i ≤ 1 0 9 1 \le a_i,b_i \le 10^9 1≤ai,bi≤109。 题解 对于输入的两个数组 A { a i ∣ i 1 , 2 , … N } , B { b i ∣ i 1 , 2 , … N } A\{a_i | i1,2,…N\},B\{b_i | i1,2,…N\} A{ai∣i1,2,…N},B{bi∣i1,2,…N}最直接的方法是用一个规格为 N × N N×N N×N 的数组去存放所有的 a i b j a_i b_j aibj 然后可采用基于选择排序的思路去选出前 N N N 个最小的值。但是这样求解的时间复杂度为 O ( N 3 ) O(N^3 ) O(N3) 这将难以通过全部测试数据。因此需要想别的办法。
如果你足够敏感你应该会立刻想到一个数据结构——堆。堆是一种建立为 O ( n ) O(n) O(n) 级、插入和删除都为 O ( l o g n ) O(logn) O(logn) 级的数据结构。显然在面对 N × N N×N N×N 个数据时用他们直接建立规格为 N × N N×N N×N 的堆依然有可能超时此时的时间复杂度为 O ( N 2 ) O(N^2) O(N2)因此需考虑别的方法。试想我们能否能利用堆的这种具有快速修改能力的数据结构来动态构建一个长度为 N N N 的数据结构并通过某种较为快速的取值方式对 N × N N×N N×N 个数据进行快速扫描并取值以更新该数据结构。为此引入偏序集
构建偏序集要求输入的数组有序。观察题中的两个数组 [ a 1 , a 2 , … , a N ] [ b 1 , b 2 , … , b N ] [a_1,a_2,…,a_N][b_1,b_2,…,b_N] [a1,a2,…,aN][b1,b2,…,bN] 它们的长度都为 N N N对这两个数组分别排序的时间复杂度最快为 O ( N l o g N ) O(N logN) O(NlogN) 这是能接受的。当输入的两个数组均有序时由所有的 a i b j a_i b_j aibj 便可以组成以下 N N N 个偏序集 { a 1 b 1 , a 1 b 2 , … , a 1 b N } { a 2 b 1 , a 2 b 2 , … , a 2 b N } … … { a N b 1 , a N b 2 , … , a N b N } \{ a_1b_1, a_1b_2, … ,a_1b_N \} \\ \{ a_2b_1, a_2b_2, … ,a_2b_N \} \\ …… \\ \{ a_Nb_1, a_Nb_2, … ,a_Nb_N \} {a1b1,a1b2,…,a1bN}{a2b1,a2b2,…,a2bN}……{aNb1,aNb2,…,aNbN}
显然在这 N N N 个偏序集中其都是有序的单调递增因此对每个单独的偏序集而言其始终满足 a i b j ≤ a i b ( j 1 ) a_ib_j≤ a_ib_{(j1)} aibj≤aib(j1)
同时可断言 a 1 b 1 a_1b_1 a1b1 为所有 a i b j a_ib_j aibj 组合中的最小值 a N b N a_Nb_N aNbN 为所有 a i b j a_ib_j aibj 组合中的最大值每个偏序集中的最小值为 a i b 1 ( i 1 , 2 , … , N ) a_ib_1 (i1,2,…,N) aib1(i1,2,…,N) 、最大值为 a i b N ( i 1 , 2 , … , N ) a_ib_N (i1,2,…,N) aibN(i1,2,…,N) 不同偏序集对应同一列的元素中始终有 a i b j ≤ a ( i 1 ) b j a_ib_j≤ a_{(i1)}b_j aibj≤a(i1)bj 。
基于偏序集的这一特性我们就能在 O ( 1 ) O(1) O(1) 的时间复杂度内从构建好的偏序集中取出当前最小值。具体的取值策略如下假设现在有一个已经构建好的长度为 N N N 的小根堆 h e a p heap heap
1、把每个偏序集中的最小元素加入小根堆 h e a p heap heap 中即 h e a p { a 1 b 1 , a 2 b 1 , … , a N b 1 } heap\{a_1b_1,a_2b_1,…,a_Nb_1\} heap{a1b1,a2b1,…,aNb1} 2、从小根堆 h e a p heap heap 中取出根元素即当前堆里的最小值假设取出的元素为 a i b j a_ib_j aibj记弹出数 13、从取出元素所在偏序集中取出仅比其小的元素即 a i b ( j 1 ) a_ib_{(j1)} aib(j1)将其插入小根堆 h e a p heap heap 中4、若弹出数不为 N N N则继续执行 2否则结束取值。
当此算法结束时我们就取出了所有 a i b j a_ib_j aibj 组合中的前 N N N小值。
正确性证明
加入偏序集元素的顺序使得我们能保证当前加入的元素是该偏序集中最小的而小根堆 h e a p heap heap 又能保证每次取出的元素是 N N N 个偏序集中未取的最小的元素中最小的所以正确性得证。
STL 模板的使用
需要注意的是在实际编码时我们不必手动构建一个堆而可以通过调用 STL 中的模板函数、数据结构来直接使用。优先队列priority_queue正是一个由 STL 提供的模板容器该队列具有普通队列所具备的一切功能不同的是优先队列采用了“堆”这一数据结构保证了该队列中的第一个元素总是整个优先队列中最大的或最小的元素默认是大根堆。 priority_queue 类的模板参数列表有三个参数
class TT 是优先队列中存储的元素的类型class Container vectorTContainer 是优先队列底层使用的存储结构可以看出来默认采用 vectorclass Compare lesstypename Container::value_type Compar是定义优先队列中元素比较方式的类。什么是优先队列中元素的比较方式前面曾提到优先队列的底层容器其实就是堆而堆中元素是存在大小关系的。比如大根堆每个结点的值都不大于它的父结点因此其堆顶元素是最大的。当我们自己定义了某些类并将由该类实例化得到的对象存进堆中时此时堆里的元素就是某个对象这时堆中元素的比较方式自然会发生改变。而编译器中的比较类只能比较内置类型所以这时就需要用户给出一个用于比较大小的模式即自定义类的比较方式并将其填充到 Compare 参数的位置。
注class Compare后跟着的lesstypename Container::value_type就是默认的比较类默认是按小于less的方式比较这种比较方式创建出来的是大根堆所以优先队列默认为大根堆。如果需要创建小堆就需要将 less 改为 greater。
lesstypename Container::value_type的定义如下
template class T
struct less: binary_function T,T,bool {bool operator() (const T x, const T y) const {return xy;}
};greatertypename Container::value_type的定义如下
template class T
struct greater: binary_function T,T,bool {bool operator() (const T x, const T y) const {return xy;}
};在这两个函数内部都重载了“( )”从而构成仿函数以便使用。 方法一 前面的算法曾提到一点当从优先队列中取出某个元素 a i b j a_ib_j aibj 时需要从该元素所在偏序集中取出仅次小于该元素的另一个元素 a i b ( j 1 ) a_ib_{(j1)} aib(j1) 填补进优先队列。理论上是这样进行取值但实际操作时我们不可能真的去建立一个 N × N N×N N×N 的二维数组作为偏序集因为这存在爆内存的可能。那要通过怎样的方式来完成这一功能呢 回看对偏序集的取数操作不难发现一点当从优先队列中弹出某个元素 a i b j a_ib_j aibj 时该元素存在两个索引即 i i i 和 j j j 其中第一个索引 i i i 指示了接下来要在 A 数组中取值的索引第二个索引在执行 j 1 j1 j1 后指示了接下来要在 B 数组中取值的索引。因此我们实际上只需要再建立 N N N 个数对为长度为N的优先队列中的每个元素各配置一个就能完成从偏序集中取所需值的需求。 对于此结构含当前数的值 value、对应在A中索引 ida、对应在B中的索引 idb共三个属性因为他足够简单因此我们可以自行构建结构体。但是需要注意一点由于这个类型的数据会被放进优先队列中因此需要为该结构指明一种比较大小的方式当然这里比较的肯定是 value这就需要重载比较运算符更进一步我们要求此优先队列是“小根堆”因此要重载的运算符是“”。下面给出基于该思路写出的 AC 代码
#includebits/stdc.h
using namespace std;// 数据声明
const int N 100005;
int n,k,a[N],b[N];// 自定义数据结构
struct NODE {int value, ida, idb;// 重载运算符bool operator(const NODE obj) const { return value obj.value;}
}node;// 定义优先队列
priority_queueNODE,vectorNODE,greaterNODE q;int main(){// 录入数据 cinn;for (int i0; in; i) cina[i];for (int i0; in; i) cinb[i];// 对数组排序 sort(a, an);sort(b, bn);// 初始化优先队列 for (int i 0; in; i)q.push({a[i]b[0], i, 0});while(n--){// 取出当前队列的最小值 nodeq.top(), q.pop();// 输出 coutnode.value ;// 从取出元素所在偏序集中选出其次元素并更改索引 idb 值 node.value a[node.ida] b[node.idb];// 入队列 q.push(node);}return 0;
} 方法二 都说 STL 是个大暖男这道题为此提供了充分的论据。 STL 提供了一个表达“数对”含义的数据结构 pair其相关属性和函数定义如下
构造函数pairtype1, type2obj(value1, value2)此函数可以声明并定义一个pair对象套娃函数make_pair( obj1, obj2)此函数可以将两个已存在的对象构造为一个新的pair类型first属性pair_obj.first 可取出对象 pair_ obj 中的第一个属性值second属性pair_obj.second 可取出对象pair_ obj 中的第二个属性值。
根据前面的分析我们知道现在需要一个含 3 个 int 类型组合在一起的数据结构而 pair 结构体能够建立一个含两个元素的类。因此为了能多加一个元素进去我们可以再多建立一重就像套娃一样再多一重pair即建立pairint, pairint, int obj。这样一来我们可设各层属性表达的含义如下
obj.first // 表示 valueobj.second.first; // 表示 idaobj.second.second // 表示 idb
如此就能根据前面的思路写出求解本题的完整代码:
#includebits/stdc.h
using namespace std;// 数据声明
const int MAX 100005;
int a[MAX], b[MAX];priority_queuepairint,pairint,int ,vector pairint,pairint,int ,greater pairint,pairint,int q;int main(){int n, tmpa, tmpb;// 录入数据 cinn;for(int i0;in;i) cina[i];for(int i0;in;i) cinb[i];// 对数组排序sort(a, an);sort(b, bn); for(int i0;in;i) q.push(make_pair(a[i]b[0], pairint,int(i, 0)));// 查找前 k 小值 while(n--){// 输出 coutq.top().first ;// 取出 ida 和 idb 索引 tmpa q.top().second.first;tmpb q.top().second.second;// 第一个元素出栈 q.pop();// 更改取出元素所在偏序集中的次元素入栈 q.push(make_pair(a[tmpa]b[tmpb1], pairint,int(tmpa, tmpb1)));}return 0;
} END
