【洛谷 P1631】 序列合并 （堆）

题目链接

直接暴力搞是\(n\)方的复杂度。\(n^2\)个数选\(n\)个最小的，容易想到堆。

我们堆里记录两个信息：到\(A\)数组哪个位置了，到\(B\)数组哪个位置了，

我直接把这两个信息存在一个\(int\)里了。

然后按\(A[i]\)+\(B[j]\)建立小根堆，每次取出堆顶并输出，然后弹出，在把这个堆顶的\(B\)数组的指针右移，加入堆，重复\(n\)次就好了。

为了降低常数，我手写了堆。

#include <cstdio>

#include <cstring>

#include <algorithm>

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

#define Close fclose(stdin);fclose(stdout);

using std::sort;

using std::swap;

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

inline int get(int x){

    return a[x / 1000] + b[x % 1000];

}

struct Heap{

    int s[100010];

    int size;

    Heap(){ size = 0; }

    void push(int x){

        int now = ++size;

        s[now] = x;

        while(now >> 1){

          if(get(s[now]) < get(s[now >> 1])) swap(s[now], s[now >> 1]);

          else break;

          now >>= 1;

        }

    }

    int top(){

        return 1[s];

    }

    void pop(){

        int now = 1, next;

        s[1] = s[size--];

        while((now << 1) <= size){

          next = now << 1;

          if(next < size && get(s[next + 1]) < get(s[next])) ++next;

          if(get(s[next]) < get(s[now])) swap(s[now], s[next]), now = next;

          else break;

        }

    }

}q;

int now;

int main(){

	Open("sequence");

	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]);

	for(int i = 1; i <= n; ++i)

	   q.push(i * 1000 + 1);

    for(int i = 1; i <= n; ++i){

       printf("%d ", get(now = q.top()));

       q.pop();

       q.push(now + 1);

    }

	return 0;

}