12108: 【原2108】配对 I

题目

题目描述

author: 蒋舜宁原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2108

Description

DS接到一个任务，这个任务有很多部分，每一个部分需要两个人完成，自然就要进行配对。

本次配对的具体要求教务处已经下发：

1) 一共\( 2 \times N \)个人，分为两个队伍，每队\( N \)人，每个人都有一个工作能力评估值（可以相同）。总共需要配出\( N \)对，每对两个人。

2) 每个人可以被配对多次，每一对中的两个人分别来自不同队伍。

3) 要求中提到，需要得到工作能力评估值之和最小的\( N \)对。

请你帮忙进行配对。

Input Format

输入共有三行。

第一行一个整数\( N \)，意义如上。

第二行有\( N \)个整数，分别表示第一个队伍中每个人的工作能力评估值。

第三行有\( N \)个整数，分别表示第二个队伍中每个人的工作能力评估值。

Output Format

共\( N \)行，每行一个整数，表示每一对的工作能力评估值之和。

按照升序输出。

Sample Input

4
2 7 4 5
8 3 1 4

Sample Output

About Test Data

对于30%数据 \(1 \leq N \leq 800\)。

对于100%数据 \(1 \leq N \leq 200,000\)。

所有工作能力评估值\(\leq 100,000,000\)。

样例解释：

2+1, 2+3, 4+1, 2+4

WashSwang's solution

#include <iostream>
#include <cstring>
using namespace std;
int n,heap[500000],p[500000],len,a[300000],b[300000],q[500000];
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\n",pop());
    return 0;
}

yyong119's solution

#include <cstdio>
#include <queue>
#include <algorithm>
// #include <map>
#define MAX_N 200010
#define KEY 10000007
using namespace std;
struct Node {
    int x, y, v;
    Node(int i = 0, int j = 0, int p = 0): x(i), y(j), v(p) {}
    bool operator<(const Node &p) const {
        return v > p.v;
    }
};
int n;
int a[MAX_N], b[MAX_N];
bool my_hash[KEY];
// map<long long, bool> um;
priority_queue<Node> q;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i) a[i] = read();
    for (register int i = 0; i < n; ++i) b[i] = read();
    sort(a, a + n); sort(b, b + n);
    q.push(Node(0, 0, a[0] + b[0]));
    for (register int i = 0; i < n; ++i) {
        // print the current minimun
        Node cur = q.top(); printf("%d\n", cur.v); q.pop();
        // solve for next possible numbers
        int x_c = cur.x, x_n = x_c + 1, y_c = cur.y, y_n = y_c + 1;
        long long x_p = ((long long) x_n << 18) | y_c, y_p = ((long long) x_c << 18) | y_n;
        int x_p_m = x_p % KEY, y_p_m = y_p % KEY;
        // (x_n, y_c) is valid and has not been in queue
        // if (x_n < n && um.find(x_p) == um.end()) {
        if (x_n < n && !my_hash[x_p_m]) {
            q.push(Node(x_n, y_c, a[x_n] + b[y_c]));
            // um[x_p] = true;
            my_hash[x_p_m] = true;
        }
        // (x_c, y_n) is valid and has not been in queue
        // if (y_n < n && um.find(y_p) == um.end()) {
        if (y_n < n && !my_hash[y_p_m]) {
            q.push(Node(x_c, y_n, a[x_c] + b[y_n]));
            // um[y_p] = true;
            my_hash[y_p_m] = true;
        }
    }
    return 0;
}