Day1-Luogu-1631

题目描述

有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2N2个和，求这N^2N2个和中最小的N个。

输入输出格式

输入格式：

第一行一个正整数N；

第二行N个整数A_iAi, 满足A_i\le A_{i+1}Ai≤Ai+1且A_i\le 10^9Ai≤109;

第三行N个整数B_iBi, 满足B_i\le B_{i+1}Bi≤Bi+1且B_i\le 10^9Bi≤109.

【数据规模】

对于50%的数据中，满足1<=N<=1000；

对于100%的数据中，满足1<=N<=100000。

输出格式：

输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。

输入输出样例

输入样例#1：复制

输出样例#1：复制

3 6 7

思路：朴素做法的复杂度不可取，那么取完前3N个肯定有前N个的答案，代码如下：

const int maxm = ;

int a[maxm], b[maxm];

int main() {

    int n;

    scanf("%d", &n);

    for (int i = ; i < n; ++i)

        scanf("%d", &a[i]);

    for (int i = ; i < n; ++i)

        scanf("%d", &b[i]);

    priority_queue<int, vector<int>, greater<int>> q;

    int l = , r = ;

    q.push(a[l] + b[r]);

    while(q.size() <=  *n) {

        if(a[l] <= b[r]) {

            l++;

            if(l >= n)

                break;

            for (int i = ; i <= r; ++i)

                q.push(a[l] + b[i]);

        } else {

            r++;

            if(r >= n)

                break;

            for (int i = ; i <= l; ++i)

                q.push(a[i] + b[r]);

        }

    }

    for (int i = ;i < n; ++i) {

        if(i)

            printf(" ");

        printf("%d", q.top());

        q.pop();

    }

    return ;

}

　看完别人的解析后，懂了一种新的做法，图示：

	a1	a2	a3	a4	a5
b1
b2
b3
b4
b5

此时N = 5, 若a3+b2是前N小，那么从a1+b1前面都是前N小，但其前面已经有N个了，则a3+b2不可能是前N小，即：(i-1)*(j-1) > N的点不可能产生贡献，代码如下：

const int maxm = ;

int a[maxm], b[maxm];

int main() {

    int n;

    scanf("%d", &n);

    for (int i = ; i < n; ++i)

        scanf("%d", &a[i]);

    for (int i = ; i < n; ++i)

        scanf("%d", &b[i]);

    priority_queue<int, vector<int>, greater<int>> q;

    for(int i = ; i < n; ++i) {

        for (int j = ; j < n; ++j) {

            if(i * j > n)

                break;

            q.push(a[i] + b[j]);

        }

    }

    for (int i = ;i < n; ++i) {

        if(i)

            printf(" ");

        printf("%d", q.top());

        q.pop();

    }

    return ;

}

还有一种通用的合并队列最小值做法，因为a[1]+b[1]<=a[2]+b[1]<= ······ 这时候将所有的含有b[1]的压入队列，将最小的出队，例如，此时出队的是a[5]+b[1]，那么下次入队的就是a[5]+b[2]，且此时的a[5]+b[2]比任何还未入队的元素都大，循环往复找到N个即可，代码如下：

const int maxm = ;

struct Node{

    int sum, ia, ib;

    Node(int _sum, int _ia, int _ib):sum(_sum), ia(_ia), ib(_ib) {}

    bool operator < (const Node &a)const {

        return a.sum < sum;

    }

};

int a[maxm], b[maxm];

int main() {

    int n;

    scanf("%d", &n);

    for (int i = ; i < n; ++i)

        scanf("%d", &a[i]);

    for (int i = ; i < n; ++i)

        scanf("%d", &b[i]);

    priority_queue<Node> q;

    for (int i = ; i < n; ++i) {

        q.push(Node(a[i] + b[], i, ));

    }

    while(n--) {

        Node tmp = q.top();

        q.pop();

        printf("%d ", tmp.sum);

        q.push(Node(a[tmp.ia] + b[tmp.ib + ], tmp.ia, tmp.ib + ));

    }

    return ;

}

巴特西

Day1-Luogu-1631

题目描述

输入输出格式

输入输出样例

最新文章

热门文章