欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1631 序列合并

程序员文章站 2024-02-14 10:07:16
...

https://www.luogu.org/problem/show?pid=1631#sub

P1631 序列合并

做法:
将 a 和 b 都从小到大排一遍序。
然后组成这样一个矩阵:
a1+b1 , a1+b2 , a1+b3 , …… , a1+bn
a2+b1 , a2+b2 , a2+b3 , ……,a2+bn
a3+b1……
……
……
an+b1 , an+b2 , an+b3 , ……,an+bn

正确性:我们先把每行的头扔进堆里,每行的头是每行中的最小值,所以这样我们能在堆里取到一个最小值。当我们取出第x行的元素时,我们就把它后面那个元素扔进堆里,因为任意时刻每行的头是这一行中最小的,所以这样我们总是能够在堆里找到当前未输出过的最小的值,正确性就能够保证了。
做法是不是很机智呢,但是不是我自己想的啊

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int n,a[100009],b[100009];
struct H{
    int k1,k2;
    int x;
    bool operator < (const H & a) const{
        return a.x<x;
    }   
};
priority_queue <H> q;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    sort(a+1,a+n+1);sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        H l;
        l.k1=i,l.k2=1,l.x=a[i]+b[1];
        q.push(l);
    } 
    int num=0;
    while(num<n)
    {
        H l=q.top();
        q.pop();
        printf("%d ",l.x);
        H p;
        p.k1=l.k1;p.k2=l.k2+1;
        p.x=a[p.k1]+b[p.k2];
        q.push(p);
        num++;
    }
    return 0;
}