嗯...

 

题目链接：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
      
        2 #include
       
         3 #include
        
          4 #include
         
           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 
          
            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 }