卿学姐与魔法(优先队列)

“你的膜法也救不了你

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

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

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

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

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

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

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

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

现在卿学姐收集了 $N$

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

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

现在卿学姐想知道，这 $N * N$

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

Input

第一行一个整数 $N$

接下来一行有 $N$

$1 \leq N \leq 100000$

$1 \leq A [i], B [i] \leq 1000000000$

Output

输出 $N$

代表 $N * N$

Sample Input

5
1 3 2 4 5 
6 3 4 1 7

Sample Output

2
3
4
4
5


//暴力二重循环也能过。。。但是，这样，这种算法还是很不错的

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 #define LL long long
 8 #define MX 100005
 9 struct Node
10 {
11     int id;
12     LL w;
13     bool operator > (const Node &b) const
14     {
15         return w<b.w;
16     }
17     bool operator < (const Node &b) const
18     {
19         return w>b.w;
20     }
21 };
22 LL a[MX];
23 LL b[MX];
24 
25 int main()
26 {
27     int n;
28     scanf("%d",&n);
29     for (int i=0;i<n;i++)
30         scanf("%lld",&a[i]);
31     for (int i=0;i<n;i++)
32         scanf("%lld",&b[i]);
33     sort(a,a+n);sort(b,b+n);
34     priority_queue<Node> Q;
35     for (int i=0;i<n;i++)
36         Q.push((Node){0,a[0]+b[i]});
37 
38     for (int i=0;i<n;i++)
39     {
40         Node tp = Q.top();Q.pop();
41         printf("%d
",tp.w);
42         Q.push((Node){tp.id+1,tp.w-a[tp.id]+a[tp.id+1]});
43     }
44     return 0;
45 }

View Code