### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4171

“十年之后，我们是朋友。”

5
1 3 2 4 5
6 3 4 1 7

2 3 4 4 5

## ligongzzz's solution

``````#include "iostream"
#include "vector"
#include "algorithm"
#include "cstdio"
using namespace std;

template <class T>
class myPriorityQueue {
vector<T> queueData;
unsigned int sizeOfQueue = 0;
bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

//向下过滤
void percolateDown(unsigned int pos) {
while (pos * 2 <= sizeOfQueue) {
if (pos * 2 + 1 > sizeOfQueue) {
//交换
if (cmp(queueData[pos * 2], queueData[pos])) {
auto temp = queueData[pos * 2];
queueData[pos * 2] = queueData[pos];
queueData[pos] = temp;
}
break;
}
else {
bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
auto temp = queueData[pos * 2 + minNum];
queueData[pos * 2 + minNum] = queueData[pos];
queueData[pos] = temp;
pos = pos * 2 + minNum;
}
else break;
}
}
}

public:
//构建
myPriorityQueue() {
queueData.clear();
queueData.push_back(*new T);
sizeOfQueue = 0;
}

//compare函数返回父结点a与孩子结点b的关系正确与否
myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
queueData.clear();
queueData.push_back(*new T);
sizeOfQueue = 0;
}

//根据数组建立堆
void buildHeap(T* eleData, unsigned int eleNum) {
queueData.clear();
sizeOfQueue = eleNum;
queueData.push_back(*new T);
for (unsigned int i = 1; i <= eleNum; i++)
queueData.push_back(eleData[i - 1]);
//向下过滤
for (unsigned int pos = eleNum / 2; pos > 0; pos--)
percolateDown(pos);
}

//判断是否空
bool empty() {
return sizeOfQueue == 0;
}

//返回队列大小
auto size() {
return sizeOfQueue;
}

//入队
void push(const T & input) {
sizeOfQueue++;
queueData.push_back(input);

//向上过滤
for (auto i = sizeOfQueue; i > 1; i = i / 2) {
//判断是否比父结点更小
if (cmp(queueData[i], queueData[i / 2])) {
//交换
auto temp = queueData[i];
queueData[i] = queueData[i / 2];
queueData[i / 2] = temp;
}
else break;
}
}

//队列最前
T top() {
return queueData[1];
}

//出队
T pop() {
auto temp = queueData[1];
queueData[1] = queueData[sizeOfQueue--];
queueData.pop_back();
percolateDown(1);
return temp;
}
};

//用于保存数据的格式
class data_type {
public:
int val = 0;
int posa = 0, posb = 0;
data_type() = default;
data_type(int val,int posa,int posb):val(val),posa(posa),posb(posb){}
bool operator<(const data_type& other) const {
return val < other.val;
}
};

int a[1000009] = { 0 }, b[1000009] = { 0 };
//构造堆
myPriorityQueue<data_type> queue_data;
//保存临时数据
data_type data_temp[1000009];
//保存答案
int ans_data[1000009];

int main() {
int num;
scanf("%d", &num);

for (int i = 0; i < num; ++i)
scanf("%d", &a[i]);
for (int i = 0; i < num; ++i)
scanf("%d", &b[i]);

sort(a, a + num);
sort(b, b + num);

//初始化堆
for (int i = 0; i < num; ++i) {
data_type temp(a[0] + b[i], 0, i);
data_temp[i] = temp;
}

queue_data.buildHeap(data_temp,num);

//进行排序和写入
for (int i = 0; i < num; ++i) {
auto temp = queue_data.pop();
//写入答案
ans_data[i] = temp.val;
//准备下一次
if (i < num - 1) {
++temp.posa;
temp.val = a[temp.posa] + b[temp.posb];
queue_data.push(temp);
}
}

//输出答案
printf("%d", ans_data[0]);
for (int i = 1; i < num; ++i)
printf(" %d", ans_data[i]);

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

int n;
int A[maxN], B[maxN];
// bool X[maxN][maxN] = {0};

struct Node {
int x;
int y;

Node(int a = 0, int b = 0) : x(a), y(b) {}

Node &operator=(const Node &right) {
if (&right != this) {
x = right.x;
y = right.y;
}

return *this;
}

bool operator<(const Node &right) const {
return ((A[x] + B[y]) < (A[right.x] + B[right.y]));
}
};

class priorityQueue {
private:
int currentSize;
Node *data;
int maxSize;

void doubleSpace();
void percolateDown(int);

public:
priorityQueue(int capacity = 10);
~priorityQueue();
void enQueue(const Node &x);
Node deQueue();
};

priorityQueue::priorityQueue(int capacity) : currentSize(0), maxSize(capacity) {
data = new Node[capacity];
}

priorityQueue::~priorityQueue() { delete[] data; }

void priorityQueue::enQueue(const Node &x) {
if (currentSize == maxSize - 2) {
doubleSpace();
}
/*if (X[x.x][x.y] == 1) {
return;
}*/

// X[x.x][x.y] = 1;

int hole = ++currentSize;
for (; hole > 1 && x < data[hole / 2]; hole /= 2) {
data[hole] = data[hole / 2];
}

data[hole] = x;
}

Node priorityQueue::deQueue() {
Node minItem;

minItem = data[1];
data[1] = data[currentSize--];
percolateDown(1);
if (minItem.x + 1 < n) {
enQueue(Node((minItem.x + 1), (minItem.y)));
}

return minItem;
}

void priorityQueue::percolateDown(int hole) {
int child;
Node tmp = data[hole];

for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;

if (child != currentSize && data[child + 1] < data[child]) {
child++;
}

if (data[child] < tmp) {
data[hole] = data[child];
} else {
break;
}
}
data[hole] = tmp;
}

void priorityQueue::doubleSpace() {
Node *tmp = data;

maxSize *= 2;

data = new Node[maxSize];
for (int i = 0; i < currentSize; i++) {
data[i] = tmp[i];
}

delete[] tmp;
}

void qSort(int *nums, int l, int h) {
if (l >= h) {
return;
}
int first = l, last = h;
int key = nums[first];

while (first < last) {
while (first < last && nums[last] >= key) {
--last;
}
nums[first] = nums[last];
while (first < last && nums[first] <= key) {
++first;
}
nums[last] = nums[first];
}
nums[first] = key;
qSort(nums, l, first - 1);
qSort(nums, first + 1, h);
}

priorityQueue gold(maxN * 2);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
for (int i = 0; i < n; i++) {
cin >> B[i];
}

qSort(A, 0, (n - 1));
qSort(B, 0, (n - 1));
for (int i = 0; i < n; i++) {
gold.enQueue(Node(0, i));
}

for (int i = 0; i < n; i++) {
Node temp = gold.deQueue();
int ans = A[temp.x] + B[temp.y];
cout << ans << ' ';
}

return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstring>
using namespace std;
int n,heap[2000000],p[2000000],len,a[1000000],b[1000000],q[1000000];
void minheapify(int x){
int smallest=x,l,r;
while (true) {
l=x<<1;
r=l+1;
if (l <= len && heap[l] < heap[x]) smallest = l;
if (r <= len && heap[r] < heap[smallest]) smallest = r;
if (smallest != x) {
swap(heap[smallest],heap[x]);
swap(p[smallest],p[x]);
x = smallest;
}
else break;
}
}
int pop(){
int ret=heap[1];
q[p[1]]++;
heap[1]=a[p[1]]+b[q[p[1]]];
minheapify(1);
return ret;
}
void qsort(int l,int r){
if (l+1>=r) return;
int i=l,j=r-1,key=b[l];
while (i<j){
while (i<j&&b[j]>=key) j--;
if (i<j) b[i++]=b[j];
while (i<j&&b[i]<=key) i++;
if (i<j) b[j--]=b[i];
}
b[i]=key;
qsort(l,i);
qsort(i+1,r);
}
int main() {
scanf("%d",&n);
for (int i=0;i<n;++i) scanf("%d",&a[i]);
for (int i=0;i<n;++i) scanf("%d",&b[i]);
qsort(0,n);
len=n;
for (int i=1;i<=n;++i)
{
heap[i]=a[i-1]+b[0];
p[i]=i-1;
q[i]=0;
}
for (int i=n>>1;i>=1;--i) minheapify(i);
for (int i=0;i<n;++i)
printf("%d ",pop());
return 0;
}
``````