目录见右上
站内文章欢迎各位转载,但是请注明出处(毕竟码字很辛苦哈)。

主题

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.


这个题似乎很经典的样子。突然又感觉到了堆的一些好处。

才觉得初等数据结构也是挺有趣的。

评论
热度(1)
©主题 —— Powered by LOFTER