Xếp đoạn

Cho N đoạn thẳng trên trục số với các điểm đầu x_i là những số nguyên trong khoảng -1000..1000 và độ dài d_i là những số nguyên dương trong khoảng 1..1000,  i = 1..N. Tính tổng chiều dài các đoạn đó phủ trên trục số.

DOAN.INP	OUTPUT		Dữ liệu vào: tệp văn bản DOAN.INP Dòng đầu tiên: số tự nhiên 1 < N £ 1000. Dòng thứ i trong N dòng tiếp theo, mỗi dòng chứa hai số nguyên ai  di cách nhau qua dấu cách, biểu thị điểm đầu và chiều dài của đoạn thứ i, i = 1..N.  Dữ liệu ra: hiển thị trên màn hình tổng chiều dài t các đoạn phủ trên trục số.
5 3 5 -11 3 -20 4 -12 8 2 5	28

Thuật toán

Phương pháp: tham.       

Sắp tăng các đoạn theo điểm đầu x.

Ta dùng kí hiệu [x,y] biểu diễn cho đoạn thẳng có điểm đầu x và điểm cuối y, x:d biểu diễn cho đoạn thẳng có điểm đầu x và chiều dài d. Ta định nghĩa một làn là đoạn tạo bởi các đoạn giao nhau liên tiếp. Hai đoạn [a,b] và [c,d] được gọi là giao nhau nếu chúng có điểm chung. Điều kiện này có nghĩa điểm đầu của đoạn này nằm trong đoạn thứ hai, tức là a £ c £ b hoặc c £ a £ d.  Do các đoạn đã được sắp tăng theo điểm đầu x nên hai đoạn x_i:d_i và x_j:d_j sẽ giao nhau khi và chỉ khi   x_j £ x_i +  d_i. Để ý rằng x_i +  d_i  là điểm cuối của đoan i. Nếu hai đoạn i và j giao nhau thì ta hợp chúng thành một đoạn [a,b] với a = x_i  và b  = max(x_i + d_i, x_j+d_j). Kết hợp các đoạn giao nhau liên tiếp đến mức tối đa ta thu được một làn gọi là làn tối đại [a,b] có chiều dài b  –  a. 

Ta khởi trị làn [a, b] bằng đoạn đầu tiên x₁:d₁, cụ thể là a := x₁, b := x₁+d₁  (= a + d₁).

Với mỗi đoạn i := 2..N ta xét:

   - Nếu đoạn i giao với làn [a,b], tức là x_i £ b thì ta hợp đoạn i với làn để tạo ra làn mới [a,b] bằng cách chỉnh b := max(b, x_i + d_i) .

                   - Nếu đoạn i không giao với làn [a,b] thì ta cộng tích lũy chiều dài của làn [a,b] hiện có vào biến tổng t rồi sinh ra làn mới từ đoạn i.

                                                                                t := t + (b – a);

                                                                                a := x_i ; b := a + d_i;

Sau khi kết thúc duyệt các đoạn ta cộng nốt làn cuối cùng vào tổng t bằng thao tác t := t + (b – a).

Độ phức tạp: O(N.logN) – chi phí cho sắp xếp Qsort.   

(*  Pascal  *)

(**************************************

               Xep doan

***************************************)

program XepDoan;

uses crt;

const

 bl = #32;  fn = 'DOAN.INP';  mn = 1001;

type KieuDoan = record x: integer; d: integer; end;

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

var  c: md1; { chua cac doan }

     n: integer;

     f: text;

procedure Doc;

 var i: integer;

begin

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

  for i := 1 to n do readln(f,c[i].x,c[i].d);

  close(f);

end;

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

     Sap tang cac doan theo

     diem dau x

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

procedure Qsort(t,p: integer): tự viết;

function max(a,b: integer): tự viết

function Tong: longint;

var t: longint; { tong do dai }

    a, b: integer; { lan [a, b] }

    i: integer;

begin

  t := 0;

  a := c[1].x; b := a + c[1].d; { Khoi tri lan }

  for i := 2 to n do

    if (c[i].x <= b) then b := max(b,c[i].x + c[i].d)

     else

     begin

       t := t + (b - a);

       a := c[i].x; b := a + c[i].d;

     end;

  Tong := t + (b - a);

end;

BEGIN

  Doc; Qsort(1,n); writeln(Tong);

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH