Phủ đoạn 1

Cho N đoạn thẳng trên trục số với các điểm đầu a_i và điểm cuối b_i là những số nguyên trong khoảng -1000..1000, a_i < b_i. Hãy chỉ ra ít nhất K đoạn thẳng sao cho khi đặt chúng trên trục số thì có thể phủ kín đoạn [x, y] với tọa độ nguyên cho trước.

DOAN.INP	DOAN.OUT	Dữ liệu vào: tệp văn bản DOAN.INP: xem bài trước Dữ liệu ra: tệp văn bản DOAN.OUT Dòng đầu tiên: số  K, nếu vô nghiệm K = 0. Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng phủ kín đoạn [x, y]. Thí dụ này cho biết ít nhất là 3 đoạn 1, 3 và 4 sẽ phủ kín đoạn [3, 23].
5 3 23 1 15 3 10 8 20 17 25 2 7	3 1 3 4

Thuật toán

Phương pháp: Tham

Sắp các đoạn tăng theo đầu phải b.

k : = 1; { chỉ số đầu tiên }

v := x; { Đầu trái của đoạn [x,y] }

Lặp đến khi  v ³ y

                   Duyệt ngược từ N đến k

                   Tìm đoạn  j  [a_j, b_j] đầu tiên có đầu trái a_j £  v;

        Nếu không tìm được: vô nghiệm;

        Nếu tìm được:

                   Ghi nhận đoạn j;

                   Đặt lại v  :=  b_j;

                   Đặt lại k := j+1;

Độ phức tạp: N².

(*  Pascal  *)

 (*========================================

                Phu doan 1

      Tìm ít nhất K đoạn có thể phủ kín

           đoạn [x,y] cho trước

  =========================================*)

program PhuDoan1;

uses crt;

const

  mn = 2002; bl = #32; nl = #13#10;

  fn = 'doan.inp'; gn = 'doan.out';

type

  KieuDoan = record

               a,b: integer;

               id: integer; { Chỉ số đoạn }

              end;

  md1 = array[0..mn] of KieuDoan;

  mi1 = array[0..mn] of integer;

var n: integer; { n - so luong doan }

    d: md1; { cac doan }

    f,g: text;

    t: mi1;

    x, y: integer; { Doan can phu }

procedure Doc;

 var i: integer;

begin

  assign(f,fn); reset(f); readln(f,n);

  readln(f,x, y);

  for i := 1 to n do

   begin

     readln(f,d[i].a,d[i].b);

     d[i].id := i;

   end;

  close(f);

end;

procedure Qsort(l,r: integer): tự viết

(*----------------------------------------

   Duyet nguoc cac doan d[s..e]

   tim doan i dau tien thoa d[i].a <= x

  ---------------------------------------*)

function Tim(s,e,x: integer): integer;

var i: integer;

begin

  Tim := 0;

  for i := e downto s do

    if (d[i].a <= x) then

      begin

        Tim := i;

        exit;

      end;

end;

procedure Ket(k: integer): tự viết

procedure XuLi;

var i,j,k,v: integer; { k - so doan tim duoc }

begin

  v := x;

  k := 0; t[k] := 0;

  repeat

    j := Tim(t[k]+1,n,v);

    if (j = 0) then { Khong tim duoc }

       begin  Ket(0); { vo nghiem } exit;  end;

    v := d[j].b; k := k + 1; t[k] := j;

  until (v >= y);

  Ket(k); { co nghiem }

end;

BEGIN

  doc; qsort(1,n); xuli;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH