注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]序列合并  

2015-06-29 18:06:33|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:堆。

Link&Limit


        [洛谷1631]
        时间限制:1000ms  空间限制:131072kb

Description


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

Input Format


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

Output Format


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

Sample Input #1


3
2 6 6
1 4 8

Sample Output #1


3 6 7

Hint


        对于50%的数据,满足1<=N<=1000;
        对于100%的数据,满足1<=N<=100000。

        堆的基础题。首先分别将A序列与B序列从小到大排序,取a[1]+b[1],a[2]+b[1]...a[n]+b[1]加入小根堆。每次取出堆顶元素a[x]+b[y],输出后将a[x]+b[y+1]重新放入堆中即可。类似的题目还有很多:求多个函数前i个最小函数值、求由规定的几个质数相乘得到的前i个最小数等等。

#include <cstdio>
struct node
{
    int a,b,sum;
    node operator = (node x)
    {
        a = x.a;
        b = x.b;
        sum = x.sum;
        return *this;
    }
};
struct heap
{
    node h[200100];
    int tot;
    heap() { tot = 0;}
   
    void add(node x)
    {
        int i = ++tot,j = i>>1;
        h[tot] = x;
        for(;i>1;i=j,j>>=1)
        {
            if(x.sum<h[j].sum) {h[i] = h[j]; h[j] = x;}
            else break;
        }
    }
   
    void del()
    {
        int i = 1,j = 2;
        node x = h[1] = h[tot--];
        for(;j<=tot;i=j,j<<=1)
        {
            if(j<tot) if(h[j+1].sum<h[j].sum) j++;
            if(x.sum>h[j].sum) {h[i] = h[j]; h[j] = x;}
            else break;
        }
    }
}heaps;

int n,a[100010],b[100010];

int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++) scanf("%d",&b[i]);
    for(i=1;i<=n;i++)
    {
        node x;
        x.a = i; x.b = 1; x.sum = a[i]+b[1];
        heaps.add(x);
    }
    for(i=1;i<=n;i++)
    {
        printf("%d ",heaps.h[1].sum);
        node x;
        x.a = heaps.h[1].a; x.b = heaps.h[1].b+1; x.sum = a[x.a]+b[x.b];
        heaps.add(x); heaps.del();
    }
    return 0;
}

  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018