LUOGU P1631

作者: ffacs 分类: 题目 发布时间: 2019-12-31 03:42

https://www.luogu.org/problemnew/show/P1631

Problem Description

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

Input

​ 第一行一个正整数N;

​ 第二行N个整数\(A_I\), 满足\(A_i \leq A_{i+1}\)\(A_i \leq 10^9\)

​ 第三行N个整数\(B_I\), 满足\(B_i \leq B_{i+1}\)\(B_i \leq 10^9\)

【数据规模】

​ 对于50%的数据中,满足1<=N<=1000;

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

Output

​ 输出仅一行,包含N个整数,从小到大输出这N个最小的和,相邻数字之间用空格隔开。 ## Solution ​ 啊我做了一个小时,然后被zech十分钟爆切了。刚开始是想遍历一下搜最小,后来才想到可以优先队列。(还是因为暴力遍历写出bug了才想换个方法,暴力的复杂度也是不对的)

我们可以记录一下数组a里每一个数当前和b里的哪一个数加起来是最小,然后找到全部最小里的最小,然后把它对应的b变成b+1(因为题目里说了是单调的)

然后就弄个结构体,重载一下小于号。

#include<bits/stdc++.h>
#define rg register
#define il inline
using namespace std;
typedef long long ll;
ll read(){
    ll ans = 0,flag = 1; char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch =='-') flag=-1;
    ans = ch ^ 48;
    while((ch=getchar())>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+(ch^48);
    return flag*ans;
}
void WRI(ll x){
    if(x<0){ putchar('-');x=-x; }
    if(x>9) WRI(x/10);
    putchar(x%10+'0');
}
void write(int x,char o){ WRI(x),putchar(o); }
int n=read(),a1[100005],b1[100005];
struct node{
    int a,b;
    bool operator < (const node& x) const{
        return a1[x.a]+b1[x.b]<a1[a]+b1[b];
    }
    node(int a,int b){ this->a=a,this->b=b; }
};
int main(){
    priority_queue<node> q;
    for(rg int i=0;i<n;i++) a1[i]=read(),q.push(node(i,0));
    for(rg int i=0;i<n;i++) b1[i]=read();
    for(rg int i=0;i<n;i++){
        node tem=q.top();q.pop();
        //cout<<tem.a<<' '<<tem.b+1<<endl;
        cout<<a1[tem.a]+b1[tem.b]<<' ';
        q.push(node(tem.a,tem.b+1));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注