洛谷 P1631 序列合并

嗯...

题目链接：https://www.luogu.org/problem/P1631

这道题很明显的是一个堆的问题，要开一个结构体的堆（结构体中记录下标、内容、个数）...

首先，把A和B两个序列分别从小到大排序，变成两个有序队列。

然后从A和B中各任取一个数相加得到N2个和，可以把这些和看成形成了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]

接下来，就相当于要将这N个有序队列进行合并排序：

首先，将这N个队列的队首放入一个堆中；然后，每次取出堆中的最小值。若这个最小值来自于第k个队列，那么，就将第k个队列的下一个元素放入堆中。

时间复杂度：O(NlogN)。

细节：

1.结构体堆一定要重载运算符

2.id是这一行的第几个元素，cnt是第cnt行（也可这样理解，cnt记录第cnt个a，id记录第id个b）

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<queue>
 5 
 6 using namespace std;
 7 
 8 const int maxn = 100005;
 9 
10 int cnt;
11 
12 struct node{
13     int id, nr, cnt;
14 } p[maxn];//结构体 
15 
16 bool operator < (node x, node y){
17     return x.nr > y.nr;
18 }//重载运算符 
19 
20 priority_queue <node> q;
21 
22 int n, a[maxn], b[maxn];
23 
24 int main(){
25     scanf("%d", &n);
26     for(int i = 1; i <= n; i++){
27         scanf("%d", &a[i]);
28         p[i].id = i;
29         p[i].cnt = 1;
30     }
31     for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
32     sort(a + 1, a + n + 1);
33     sort(b + 1, b + n + 1);
34     for(int i = 1; i <= n; i++){
35         p[i].nr = a[1] + b[i];
36         q.push(p[i]);
37     }
38     for(int i = 1; i <= n; i++){
39         int ans = q.top().nr;
40         printf("%d ", ans);
41         node u;
42         u.cnt = q.top().cnt + 1;
43         u.id = q.top().id;
44         q.pop();
45         u.nr = a[u.cnt] + b[u.id];
46         q.push(u);
47     }
48     return 0;
49 }

AC代码