Codevs No.1245 最小的N个和

2016-05-31 18:52:15

题目链接: 最小的N个和 Codevs No.1245

题目大意:

　　给两个等长数列,各取一个数求和,找到最小的N组

解法:

　　堆优化的大暴力

　　直接枚举所有可能在最大堆中更新,删除最大组合

需要注意的地方:

　　1.如果任何一个加数大于等于堆顶元素,break

　　2.如果两者之和已经大于等于堆顶元素,break

 1 //最小的N个和 (Codevs No.1245)
 2 //堆(优先队列)
 3 #include<stdio.h>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int maxn=100010;
 8 priority_queue <int> q;
 9 int N;
10 int x[maxn];
11 int y[maxn];
12 int ans[maxn];
13 int main()
14 {
15     scanf("%d",&N);
16     for(int i=1;i<=N;i++)
17     {
18         scanf("%d",&x[i]);
19     }
20     for(int j=1;j<=N;j++)
21     {
22         scanf("%d",&y[j]);
23     }
24     sort(x+1,x+N+1);
25     sort(y+1,y+N+1);
26     for(int i=1;i<=N;i++)q.push(x[i]+y[i]);
27     for(int i=1;i<=N;i++)
28     {
29         if(x[i]>=q.top())break;
30         for(int j=1;j<=N;j++)
31         {
32             if(i==j)continue;
33             if(y[j]+x[i]>=q.top())break;
34             q.push(x[i]+y[j]);
35             q.pop();
36         }
37     }
38     for(int i=1;i<=N;i++)
39     {
40         ans[i]=q.top();
41         q.pop();
42     }
43     for(int i=N;i>=1;i--)
44     {
45         printf("%d ",ans[i]);
46     }
47     return 0;
48 }