1922 - 序列合并

3
2 6 6
1 4 8

3 6 7

Hint

建议用最小堆实现。

Solution C

#include <stdio.h>
#include <stdlib.h>
#define maxn 100001
#define swap(A,B,C) (C)=(A),(A)=(B),(B)=(C)
int A[maxn], B[maxn], C[maxn];
int N;
void adjust_down(int i, int n){
int j, s=C[i];
for(j = 2*i;j <= n;j *= 2){
    int temp;
    if(C[j]<=C[j+1]&&j<n)j++;
    if(s>=C[j]) break;
    swap(C[j/2],C[j],temp);
}
}

void heapsort(){
for(int i = 0;i < N - 1;i ++){
    int temp;
    swap(C[1],C[N-i],temp);
    adjust_down(1,N-i-1);
}
}

void proc(){
for(int i = 1;i <= N; i++){
    C[i]=A[1]+B[i];
}
for(int i = N/2;i >= 1; i--){
    adjust_down(i,N);
}
for(int i = 2;i <= N; i++){
    for(int j = 1;j <= N; j++){
        int temp=A[i]+B[j];
        if(temp<C[1]){
            C[1]=temp;
            adjust_down(1,N);
        }
        else{
            break;
        }
    }
}
heapsort();
for(int i = 1;i < N; i++){
    printf("%d ",C[i]);
}
printf("%d\n",C[N]);
}


int main()
{
    while(scanf("%d",&N) != EOF){
        for(int i = 1;i <=N; i++){
            scanf("%d",&A[i]);
        }
        for(int i = 1;i <= N; i++){
            scanf("%d",&B[i]);
        }
        proc();
    }
    return 0;
}

Solution C++

#pragma warning(disable: 4786)
#include<cstdio>
#include<set>
#include<vector>
using namespace std;
vector<int>a,b;
multiset<int>s;
multiset<int>::iterator it;
int main()  
{  
	int i,j,n,m;
	scanf("%d",&n);
	a.resize(n),b.resize(n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(i=0;i<n;i++)
		scanf("%d",&b[i]);
	for(i=0;i<n;i++)
		s.insert(a[0]+b[i]);
	for(i=1;i<n;i++)
	{
		it=s.end();
		it--;
		m=*it;
		for(j=0;j<n;j++)
		{
			if(a[i]+b[j]>=m)
				break;
			s.erase(it);
			s.insert(a[i]+b[j]);
			it=s.end();
			it--;
		    m=*it;
		}
	}
	for(it=s.begin();it!=s.end();it++)
	{
		if(it!=s.begin())
			printf(" ");
		printf("%d",*it);
	}
    return 0;  
}