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。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm> 
 4 #define M 100010
 5 using namespace std;
 6 int a[M],b[M],heap[M],l=0;
 7 int put(int d)  //建立堆并维护 
 8 {
 9     heap[++l]=d;
10     int next,now=l;
11     while(now>1)
12     {
13         next=now/2;
14         if(heap[now]<=heap[next])break;
15         swap(heap[now],heap[next]);
16         now=next;
17     }
18 }
19 int get()  //删除堆顶元素 
20 {
21     int now,next;
22     heap[1]=heap[l--];
23     now=1;
24     while(now*2<=l)
25     {
26         next=now*2;
27         if(next<l&&heap[next]<heap[next+1])next++;
28         if(heap[now]>=heap[next])break;
29         swap(heap[now],heap[next]);
30         now=next;
31     }
32 }
33 int main()
34 {
35     int n;
36     scanf("%d",&n);
37     for(int i=1;i<=n;i++)
38         scanf("%d",&a[i]);
39     for(int i=1;i<=n;i++)
40         scanf("%d",&b[i]);
41     sort(a+1,a+n+1);  //排序 
42     sort(b+1,b+n+1);
43     heap[1]=(a[1]+b[1]);
44     for(int i=1;i<=n;++i)
45         put(a[1]+b[i]);  //初始化 
46     for(int i=2;i<=n;i++)
47     {
48         if(a[i]+b[1]>=heap[1])break;  //因为a,b，都是递增的，所以 a[i]+b[1]>=heap[1]，以后的a会更大； 
49         for(int j=1;j<=n;j++)
50         {
51             if(a[i]+b[j]>=heap[1])continue; //因为a,b，都是递增的，所以 a[i]+b[j]>=heap[1]，以后的b会更大； 
52             put(a[i]+b[j]);
53             get();  //删除最大的，留下n个数 
54         }
55     }    
56     sort(heap+1,heap+n+1);  //从小到大排序 
57     for(int i=1;i<=n;++i)  //输出 
58         printf("%d ",heap[i]);
59     return 0;
60 }