Skip to content

14171: 【原4171】decades

题目

题目描述

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

Description

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

十年之后，一次偶然的机会，小W应Mr. Owl的邀请，来到了他位于Rusty Lake边的小屋中。Mr. Owl告诉她，作为Rusty Lake尊贵的客人，她可以乘上湖中的电梯回到过去，改变自己某件伤心的往事。电梯的动力系统需要若干金色方块才能启动，但是小屋里只有一些黑色和白色的方块。万幸，一个黑方块和一个白方块可以合成体积是两方块之和的金方块；更加神奇的是，这种合成并不会使原料消失，使用过的黑、白方块还可以与其它异色方块继续合成。把足够的金色方块放到引擎里可不是一件轻松的事情，所以小W希望得到的金色方块体积尽可能小。但小W面对数量巨大的黑白方块头昏脑涨，于是她从小屋中打电话给你，希望你帮帮她。

给出两个长度为$n$的序列$A$和$B$，在$A$和$B$中各任取一个数相加，一共可得$n^2$个和（值可以重复）。请输出其中最小的$n$个（可重复）。

Input Format

输入共三行。第一行包含一个正整数$n$，代表序列的长度；

第二行包含$n$个正整数$a_i$，代表序列$A$；

第三行包含$n$个正整数$b_i$，代表序列$B$。

Output Format

输出共一行，包含$n$个用空格隔开的整数，为最小的$n$个和。

Sample Input

5
1 3 2 4 5
6 3 4 1 7

Sample Output

2 3 4 4 5

数据规模与约定

对于$100\%$的数据，$n\le10^6$，$0\le a_i, b_i \le10^9$。

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;
}