MINROAD – spoj

Đề bài

Thuật toán

Ta lưu 2*n điểm vào mảng T:

  • T[i].d là khoảng cách đến vị trí bắt đầu của con đường
  • T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do 
 For j=F[i-1] to 2*N do ……..
Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Độ phức tạp: O(N log N).

Code

uses    math;
const   fi='';
        fo='';
        maxn=300000;
type    arra=array[0..maxn] of longint;
var     tung,cuc,d,tu,cu:arra;
        kieu:array[0..maxn] of byte;
        i,j,n,a,b:longint;
        f:text;
        res,tmp:longint;
procedure QS(l,r:longint);
Var i,j,x,w:longint;
Begin
x:=d[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(d[i]<x) do i:=i+1;
     While (x<d[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=kieu[i];kieu[i]:=kieu[j];kieu[j]:=w;
          w:=d[i];d[i]:=d[j];d[j]:=w;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,a,b);
    for i:=1 to n do
        readln(f,d[i],kieu[i]);
    close(f);
end;
procedure xuly;
var     t,c,k:longint;
begin
    t:=0; c:=0;
    qs(1,n);
    for i:=1 to n do
        if kieu[i]=1 then begin inc(t); tung[t]:=i; end
        else begin inc(c); cuc[c]:=i; end;
    for i:=1 to n do
    begin
        tu[i]:=tu[i-1];
        cu[i]:=cu[i-1];
        if kieu[i]=1 then inc(tu[i]);
        if kieu[i]=2  then inc(cu[i]);
    end;
if (tu[n]<a) or(cu[n]<b) then exit;
    i:=max(tung[a],cuc[b]);
    k:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
    res:=d[i]-d[k];
    inc(i);
    while i<=n do
    begin
        tmp:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
        if d[i]-d[tmp]<res then res:=d[i]-d[tmp];
        inc(i);
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    if res=0 then writeln(f,-1) else
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây……

Speak Your Mind

*