关键字：堆。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。
Input Format
第一行一个正整数N；
第二行N个整数Ai,满足Ai<=Ai+1且Ai<=10^9；
第三行N个整数Bi, 满足Bi<=Bi+1且Bi<=10^9.
Output Format
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
Sample Input #1
3
2 6 6
1 4 8
Sample Output #1
3 6 7
Hint
对于50%的数据，满足1<=N<=1000；
对于100%的数据，满足1<=N<=100000。
堆的基础题。首先分别将A序列与B序列从小到大排序，取a[1]+b[1]，a[2]+b[1]...a[n]+b[1]加入小根堆。每次取出堆顶元素a[x]+b[y]，输出后将a[x]+b[y+1]重新放入堆中即可。类似的题目还有很多：求多个函数前i个最小函数值、求由规定的几个质数相乘得到的 前i个最小数等等。
#include <cstdio>
struct node
{
int a,b,sum;
node operator = (node x)
{
a = x.a;
b = x.b;
sum = x.sum;
return *this;
}
};
struct heap
{
node h[200100];
int tot;
heap() { tot = 0;}
void add(node x)
{
int i = ++tot,j = i>>1;
h[tot] = x;
for(;i>1;i=j,j>>=1)
{
if(x.sum<h[j].sum) {h[i] = h[j]; h[j] = x;}
else break;
}
}
void del()
{
int i = 1,j = 2;
node x = h[1] = h[tot--];
for(;j<=tot;i=j,j<<=1)
{
if(j<tot) if(h[j+1].sum<h[j].sum) j++;
if(x.sum>h[j].sum) {h[i] = h[j]; h[j] = x;}
else break;
}
}
}heaps;
int n,a[100010],b[100010];
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<=n;i++) scanf("%d",&b[i]);
for(i=1;i<=n;i++)
{
node x;
x.a = i; x.b = 1; x.sum = a[i]+b[1];
heaps.add(x);
}
for(i=1;i<=n;i++)
{
printf("%d ",heaps.h[1].sum);
node x;
x.a = heaps.h[1].a; x.b = heaps.h[1].b+1; x.sum = a[x.a]+b[x.b];
heaps.add(x); heaps.del();
}
return 0;
}
评论 (0)
