AC日记——最小的N个和 codevs 1245

1245 最小的N个和

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

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

输入描述 Input Description

第一行输入一个正整数N；第二行N个整数Ai 且Ai≤10^9；第三行N个整数Bi，
且Bi≤10^9

输出描述 Output Description

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

样例输入 Sample Input

1 3 2 4 5
6 3 4 1 7

样例输出 Sample Output

2 3 4 4 5

数据范围及提示 Data Size & Hint

【数据规模】对于 100%的数据，满足 1≤N≤100000。

思路：

　　用堆做，手写堆；

　　先把a1+b1到a1+bn的值扔到堆中

　　然后a，b序列排序

　　堆是大根堆

　　堆里就是当前最小的n个和

　　堆顶就是当前n个和中最大的数

　　然后从a2开始循环

　　每次循环开一重新的循环

　　把b序列遍历

　　然后如果ai+bj<top，则弹出top，ai+bj入堆

　　否则跳出这层j循环进入下一个i循环

　　因为a，b的单调性，所以我们可以实现上述步骤

　　然后每次入堆都伴随着一次出堆

　　所以，最后一定是n个

　　按倒序输出轻松ac

来，上代码：

#include <cstdio>
#include <algorithm>

using namespace std;

class T_heap {
    private:
        int heap[500001],n;
        
    public:
        void up(int now)
        {
            if(now<=1) return ;
            int front=now>>1;
            if(heap[front]>heap[now])
            {
                swap(heap[front],heap[now]);
                up(front);
            }
        }
        
        void down(int now)
        {
            if(now>n) return;
            int vlc,vrc,next=now;
            bool blc,brc;
            if((now<<1)<=n) blc=true,vlc=heap[now<<1];
            else blc=false;
            if((now<<1|1)<=n) brc=true,vrc=heap[now<<1|1];
            else brc=false;
            if(blc)
            {
                if(vlc<heap[next])
                {
                    next=now<<1;
                }
            }
            if(brc)
            {
                if(vrc<heap[next])
                {
                    next=now<<1|1;
                }
            }
            if(next!=now)
            {
                swap(heap[next],heap[now]);
                down(next);
            }
        }
        
        void push(int cur_)
        {
            n++;
            heap[n]=cur_*-1;
            up(n);
        }
        
        void pop()
        {
            heap[1]=heap[n];
            n--;
            down(1);
        }
        
        int top()
        {
            return heap[1]*-1;
        }
};
class T_heap que;

int n,if_z,ai[100001],bi[100001];

char Cget;

inline void read_int(int &now)
{
    now=0,if_z=1;Cget=getchar();
    while(Cget>'9'||Cget<'0')
    {
        if(Cget=='-') if_z=-1;
        Cget=getchar();
    }
    while(Cget<='9'&&Cget>='0')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }
    now*=if_z;
}

int main()
{
    read_int(n);
    for(int i=1;i<=n;i++)
    {
        read_int(ai[i]);
    }
    sort(ai+1,ai+n+1);
    for(int i=1;i<=n;i++)
    {
        read_int(bi[i]);
        que.push(ai[1]+bi[i]);
    }
    sort(bi+1,bi+n+1);
    for(int i=2;i<=n;i++)
    {
        int top_=que.top();
        for(int j=1;j<=n;j++)
        {
            if(ai[i]+bi[j]<top_)
            {
                que.pop();
                que.push(ai[i]+bi[j]);
                top_=que.top();
            }
            else break;
        }
    }
    for(int i=n;i>=1;i--)
    {
        ai[i]=que.top();
        que.pop();
    }
    for(int i=1;i<=n;i++) printf("%d ",ai[i]);
    return 0;
}