2016-05-31 18:52:15
题目链接: 最小的N个和 Codevs No.1245
题目大意:
给两个等长数列,各取一个数求和,找到最小的N组
解法:
堆优化的大暴力
直接枚举所有可能在最大堆中更新,删除最大组合
需要注意的地方:
1.如果任何一个加数大于等于堆顶元素,break
2.如果两者之和已经大于等于堆顶元素,break
//最小的N个和 (Codevs No.1245)
//堆(优先队列)
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
priority_queue <int> q;
int N;
int x[maxn];
int y[maxn];
int ans[maxn];
int main()
{
scanf("%d",&N);
for(int i=;i<=N;i++)
{
scanf("%d",&x[i]);
}
for(int j=;j<=N;j++)
{
scanf("%d",&y[j]);
}
sort(x+,x+N+);
sort(y+,y+N+);
for(int i=;i<=N;i++)q.push(x[i]+y[i]);
for(int i=;i<=N;i++)
{
if(x[i]>=q.top())break;
for(int j=;j<=N;j++)
{
if(i==j)continue;
if(y[j]+x[i]>=q.top())break;
q.push(x[i]+y[j]);
q.pop();
}
}
for(int i=;i<=N;i++)
{
ans[i]=q.top();
q.pop();
}
for(int i=N;i>=;i--)
{
printf("%d ",ans[i]);
}
return ;
}