题目

传送门＝￣ω￣＝

题目描述

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

输入输出格式

输入格式：

第一行一个正整数 N；

第二行 N 个整数 Ai, 满足 Ai<=Ai+1 且 Ai<=10^9;

第三行 N 个整数 Bi, 满足 Bi<=Bi+1 且 Bi<=10^9.

【数据规模】

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

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

输出格式：

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

输入输出样例

输入样例 #1：

3
2 6 6
1 4 8

输出样例 #1：

3 6 7

题解

首先 a、b 从小到大排序。
众所周知，最小的数字就是 $a[1]+b[1]$
那么第二个数字一定是 $a[1]+b[2]$ 、 $a[2]+b[1]$ 中的一个！
所以设当前最小的是 $a[l]+b[r]$
那么下一个答案就存在于 $a[l]+b[r+1]$ 和 $a[l+1]+b[r]$ 中。
所以我们搞个优先队列，每次取出最小的输出，并对它进行扩展。
复杂度 $O(nlogn)$

优先队列 STL 自带。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename tp>void in(tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,a[100005],b[100005],ans[100005];
set<int> book[100005];
struct node
{
    int l,r;
    bool operator < (node oth)const{return a[oth.l]+b[oth.r]<a[l]+b[r];}
};
priority_queue<node> pq;
int main()
{
    in(n);
    for(int i=1;i<=n;in(a[i++]));
    for(int i=1;i<=n;in(b[i++]));
    sort(b+1,b+1+n),sort(a+1,a+1+n),pq.push((node){1,1});
    for(int i=1;i<=n;i++)
    {
        node f=pq.top();pq.pop();
        printf("%d ",a[f.l]+b[f.r]);
        if(f.l<n&&!book[f.l+1].count(f.r))
            pq.push((node){f.l+1,f.r}),book[f.l+1].insert(f.r);
        if(f.r<n&&!book[f.l].count(f.r+1))
            pq.push((node){f.l,f.r+1}),book[f.l].insert(f.r+1);
    }
    return 0;
}

【题解】序列合并 STL 优先队列 LUOGU – 1631

于2017年4月11日2017年4月11日由XZYQvQ发布

题目

题目描述

输入输出格式

输入输出样例

题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】序列合并 STL 优先队列 LUOGU – 1631

于2017年4月11日2017年4月11日由XZYQvQ发布

题目

题目描述

输入输出格式

输入输出样例

题解

XZYQvQ

0 条评论

发表回复 取消回复

发表回复取消回复