地址：http://acm.uestc.edu.cn/#/problem/show/1329
题目：
卿学姐与魔法
Time Limit: 1200/800MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
“你的膜法也救不了你”——蛤
在去拯救公主的道路上，卿学姐披荆斩棘，刀刃早已锈迹斑斑。
一日卿学姐正在为武器的问题发愁，碰到了正在赏树的天行廖。
天行廖嘴角微扬，似乎看穿了卿学姐的心思，故意在此等待。
“少年，你渴望掌握雷电的力量吗？”天行廖如是问道。
已经差不多是条咸鱼的卿学姐欣然答应了。于是卿学姐开始跟随魔法大师天行廖学习魔法的力量。
刚入门的卿学姐发现，每个魔法都是由两种基本元素构成的，A元素和B元素。
而每个魔法的魔力是合成这个魔法的A元素和B元素的大小的和。
例如一个大小为3的A元素和一个大小为6的B元素，能构成一个魔力为9的魔法。
现在卿学姐收集了NN个A元素和NN个B元素。
敏锐的卿学姐立刻发现他能组合出N∗NN∗N种魔法。
谦虚的卿学姐并不希望自己太跳，所以他准备将这N∗NN∗N种魔法中的最小的NN种展示给天行廖检查。
现在卿学姐想知道，这N∗NN∗N种魔法中最小的NN种是什么。
当然，得从小到大输出哦~
Input
第一行一个整数NN
接下来一行有NN个数，表示NN个A元素
接下来一行有NN个数，表示NN个B元素
1≤N≤1000001≤N≤100000
1≤A[i],B[i]≤10000000001≤A[i],B[i]≤1000000000
Output
输出NN行，每行一个整数
代表N∗NN∗N种魔法中最小的NN个
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 |
2 |
思路：
就是先把A[i]+B[0]拖进一个优先队列，然后每次取出最小值A[i]+B[k]，同时把A[i]+B[k+1]扔进去，然后直到取出n个数。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cstdlib>
#include <string> #define PI acos((double)-1)
#define E exp(double(1))
using namespace std;
int a[],b[];
int c[]; int main (void)
{
int n;
cin>>n;
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a+n+);
for(int i=;i<=n;i++)
scanf("%d",&b[i]);
sort(b+,b+n+);
priority_queue<pair<int,int> >s;
for(int i=;i<=n;i++)
s.push(make_pair(-(a[i]+b[]),));
for(int i=;i<=n;i++)
{
pair<int,int> temp=s.top();s.pop();
c[i]=-temp.first;
int k=temp.second;
if(temp.second<n)s.push(make_pair(-(-temp.first-b[k]+b[k+]),k+));
}
for(int i=;i<=n;i++)
printf("%d\n",c[i]);
return ;
} //struct node
//{
// int sum,b;
// node(int a,int b):sum(a),b(b){}
// bool operator<(node &a)const
// {
// return sum>a.sum;
// }
//};