卿学姐与魔法

Time Limit: 1200/800MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

“你的膜法也救不了你”——蛤

在去拯救公主的道路上，卿学姐披荆斩棘，刀刃早已锈迹斑斑。

一日卿学姐正在为武器的问题发愁，碰到了正在赏树的天行廖。

天行廖嘴角微扬，似乎看穿了卿学姐的心思，故意在此等待。

“少年，你渴望掌握雷电的力量吗？”天行廖如是问道。

已经差不多是条咸鱼的卿学姐欣然答应了。于是卿学姐开始跟随魔法大师天行廖学习魔法的力量。

刚入门的卿学姐发现，每个魔法都是由两种基本元素构成的，A元素和B元素。

而每个魔法的魔力是合成这个魔法的A元素和B元素的大小的和。

例如一个大小为3的A元素和一个大小为6的B元素，能构成一个魔力为9的魔法。

现在卿学姐收集了

敏锐的卿学姐立刻发现他能组合出

谦虚的卿学姐并不希望自己太跳，所以他准备将这

现在卿学姐想知道，这

当然，得从小到大输出哦~

Input

第一行一个整数

接下来一行有

Output

输出

代表

Sample input and output

Sample Input	Sample Output
5 1 3 2 4 5 6 3 4 1 7	2 3 4 4 5

思路：

就是先把A[i]+B[0]拖进一个优先队列，然后每次取出最小值A[i]+B[k]，同时把A[i]+B[k+1]扔进去，然后直到取出n个数。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <queue>
 7 #include <stack>
 8 #include <map>
 9 #include <vector>
10 #include <cstdlib>
11 #include <string>
12 
13 #define PI acos((double)-1)
14 #define E exp(double(1))
15 using namespace std;
16 int a[100000],b[100000];
17 int c[100000];
18 
19 int main (void)
20 {
21     int n;
22     cin>>n;
23     for(int i=1;i<=n;i++)
24         scanf("%d",&a[i]);
25     sort(a+1,a+n+1);
26     for(int i=1;i<=n;i++)
27         scanf("%d",&b[i]);
28     sort(b+1,b+n+1);
29     priority_queue<pair<int,int> >s;
30     for(int i=1;i<=n;i++)
31         s.push(make_pair(-(a[i]+b[1]),1));
32     for(int i=1;i<=n;i++)
33     {
34         pair<int,int> temp=s.top();s.pop();
35         c[i]=-temp.first;
36         int k=temp.second;
37         if(temp.second<n)s.push(make_pair(-(-temp.first-b[k]+b[k+1]),k+1));
38     }
39     for(int i=1;i<=n;i++)
40         printf("%d
",c[i]);
41     return 0;
42 }
43 
44 
45 //struct node
46 //{
47 //    int sum,b;
48 //    node(int a,int b):sum(a),b(b){}
49 //    bool operator<(node &a)const
50 //    {
51 //        return sum>a.sum;
52 //    }
53 //};

View Code