1245 最小的N个和
题目描述 Description
有两个长度为 N 的序列 A 和 B,在 A 和 B 中各任取一个数可以得到 N^2 个和,求这N^2 个和中最小的 N个。
输入描述 Input Description
第一行输入一个正整数N;第二行N个整数Ai 且Ai≤10^9;第三行N个整数Bi,
且Bi≤10^9
输出描述 Output Description
输出仅一行,包含 n 个整数,从小到大输出这 N个最小的和,相邻数字之间用
空格隔开。
样例输入 Sample Input
5
1 3 2 4 5
6 3 4 1 7
样例输出 Sample Output
2 3 4 4 5
数据范围及提示 Data Size & Hint
【数据规模】 对于 100%的数据,满足 1≤N≤100000。
个人解法:
首先把A和B排序。
最小的和显然是A[1]+B[1]
接下来把这个和输出之后,把A[1]+B[1]删去。第二大的和可能是A[1]+B[2],也可能是A[2]+B[1]。
接下来取出这两个和中较小的一个,假设是A[x]+B[y],就把A[x+1]+B[y]与A[x]+B[y+1]加入待定数组中。
……
不断模拟,直到找到n个和。
这是可以贪心证明的(可以画一个表格来看)。如果乘法也是可以这样做的。
注意判重,也就是同一个A[x]+B[y]不要重复加入。
例如下面的例子:
5
649 952 137 73 990
128 717 55 641 476
跑出来应该是
128 192 201 265 549
代码如下:
type
inf1=record
x,y:longint;
sum:int64;
end;
inf2=record
x,y,next:longint;
end;
var
Hash:array[0..100047] of longint;//Hash表储存拓展的位置
E:array[1..300000] of inf2;
A:array[0..1,1..100010] of int64;//A与B统一储存在A中,一个是A[0]一个是A[1]
Heap:array[1..100010] of inf1;//堆
n,i,tot,x,y,top:longint;
procedure swap(var a,b:longint);//交换
var
c:longint;
begin
c:=a;
a:=b;
b:=c;
end;
procedure int64swap(var a,b:int64);//交换
var
c:int64;
begin
c:=a;
a:=b;
b:=c;
end;
function H(x,y:longint):longint;//Hash函数
var
tmp:int64;
begin
tmp:=(x shr 1)*(y shl 1) mod 100047;
tmp:=(tmp+x+y) mod 100047;
exit(tmp);
end;
procedure ins(x,y:longint);//插入位置(x,y)
var
v:longint;
begin
v:=H(x,y);
inc(top);
E[top].x:=x;
E[top].y:=y;
E[top].next:=hash[v];
Hash[v]:=top;
end;
function query(x,y:longint):boolean;//查询位置(x,y)是否已经被拓展过了
var
v:longint;
begin
v:=H(x,y);
v:=Hash[v];
while v<>0 do
begin
if (E[v].x=x) and (E[v].y=y) then exit(true);
v:=E[v].next;
end;
exit(false);
end;
procedure Sort(ifdo,l,r:longint);//排序
var
tl,tr,x:longint;
begin
tl:=l;
tr:=r;
x:=A[ifdo,l+random(r-l+1)];
repeat
while A[ifdo,tl]<x do inc(tl);
while A[ifdo,tr]>x do dec(tr);
if tl<=tr then
begin
int64swap(A[ifdo,tl],A[ifdo,tr]);
inc(tl);
dec(tr);
end;
until tl>tr;
if l<tr then Sort(ifdo,l,tr);
if tl<r then Sort(ifdo,tl,r);
end;
procedure UP(num,max:longint);//上调
var
j:longint;
begin
j:=num shr 1;
while j>0 do
begin
if Heap[j].sum>Heap[num].sum then
begin
swap(Heap[j].x,Heap[num].x);
swap(Heap[j].y,Heap[num].y);
int64swap(Heap[j].sum,Heap[num].sum);
num:=j;
j:=j shr 1;
end
else j:=0;
end;
end;
procedure Down(num,max:longint);//下调
var
j:longint;
begin
j:=num shl 1;
while j<=max do
begin
if (j<max) and (Heap[j].sum>Heap[j+1].sum) then inc(j);
if Heap[num].sum>Heap[j].sum then
begin
swap(Heap[num].x,Heap[j].x);
swap(Heap[num].y,Heap[j].y);
int64swap(Heap[num].sum,Heap[j].sum);
num:=j;
j:=j shl 1;
end
else j:=max+1;
end;
end;
procedure delete(p:longint);//删除节点
begin
swap(Heap[tot].x,Heap[p].x);
swap(Heap[tot].y,Heap[p].y);
int64swap(Heap[tot].sum,Heap[p].sum);
Heap[tot].x:=0;
Heap[tot].y:=0;
Heap[tot].sum:=0;
dec(tot);
Down(p,tot);//由于p是1,所以不需要考虑上调
end;
begin
read(n);
for i:=1 to n do
read(A[0,i]);
for i:=1 to n do
read(A[1,i]);//读入
randomize;
Sort(0,1,n);
Sort(1,1,n);//排序
Heap[1].x:=1;
Heap[1].y:=1;
Heap[1].sum:=A[0,1]+A[1,1];
ins(1,1);//初始化,把A[1]+B[1]扔进堆去
tot:=1;
for i:=1 to n do
begin
x:=Heap[1].x;
y:=Heap[1].y;
write(Heap[1].sum,' ');//输出
delete(1);
if not query(x+1,y) then//插入
begin
inc(tot);
Heap[tot].x:=x+1;
Heap[tot].y:=y;
Heap[tot].sum:=A[0,x+1]+A[1,y];
ins(x+1,y);
UP(tot,tot);
end;
if not query(x,y+1) then//插入
begin
inc(tot);
Heap[tot].x:=x;
Heap[tot].y:=y+1;
Heap[tot].sum:=A[0,x]+A[1,y+1];
ins(x,y+1);
UP(tot,tot);
end;
end;
end.
这个题似乎很经典的样子。突然又感觉到了堆的一些好处。
才觉得初等数据结构也是挺有趣的。