Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Cho N đoạn thẳng trên trục số với các điểm đầu xi là những số nguyên trong khoảng -1000..1000 và độ dài di 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 xvà đ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 xi:dixj:dj sẽ giao nhau khi và chỉ khi   xj£xi +  di. Để ý rằng xi +  di  là điểm cuối của đoan i. Nếu hai đoạn ij giao nhau thì ta hợp chúng thành một đoạn [a,b] với a = xi  b  = max(xi+ di, xj+dj). 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 x1:d1, cụ thể là a := x1, b := x1+d1  (= a+ d1).
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à xi £ 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, xi + di) .
                   - 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 := xi ; b := a + di;
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
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts