| Đăng nhập qua LiketLy 

trả lời
  • Câu trả lời được chấp nhận

    Nhận xét:

    - Mục tiêu của bài toán này là giảm số đoạn xích từ n về 1 (bằng cách chặt ra - hàn lại) trong một khoảng thời gian ngắn nhất.

    - Thời gian thông thường để giảm đi 1 đoạn xích bằng 2 đơn vị (chặt-hàn), tức là ta chặt 1 mắt xích trong đoạn xích A, nối đoạn xích B vào, rồi hàn lại => số đoạn xích giảm đi 1, và thời gian thực hiện là 2.

    - Riêng với đoạn xích có độ dài 1, cùng với 2 đơn vị thời gian (chặt-hàn), ta có thể làm giảm số đoạn xích đi 2. Ví dụ đoạn xích A có độ dài 1, ta chặt A ra, rồi lấy mắt xích đó đi hàn 2 đoạn xích B&C => số đoạn xích giảm đi 2 trong 2 đơn vị thời gian.

    - Với đoạn xích có độ dài lớn hơn 1, nếu ta liên tục chặt mắt của nó đem đi nối các đoạn xích khác (không dùng mắt đó để nối nó), thì mỗi lần chặt-hàn đó ta cũng giảm được 1 đoạn xích, riêng lần chặt hàn cuối cùng thì giảm được 2 đoạn xích, do lúc đó nó đã là đoạn xích có độ dài 1 => cách làm này tối ưu hơn cách chặt 1 mắt ra rồi nối thẳng nó vào đoạn xích khác

    - Nếu ta chặt đoạn xích có độ dài lớn hơn 1 ở giữa (không chặt từ 1 đầu), thì số đoạn xích độ dài 1 thu được sẽ nhiều hơn, nhưng thời gian không tối ưu hơn chặt từ 1 đầu chặt vào, do bản thân thao tác chặt từ giữa lại làm tăng số đoạn xích chưa nối lên (có thể chứng mình rằng hai cách chặt đem lại thời gian bằng nhau).

    Thuật toán:

    - Sắp xếp số đoạn xích tăng dần

    - Luôn xử lý các đoạn xích có độ dài bằng 1 theo cách chặt ra rồi đem đi nối 2 đoạn xích khác

    - Xử lý chặt từ đoạn xích ngắn nhất, tăng dần khi không còn đoạn xích ngắn hơn. Chặt các đoạn xích ngắn (có độ dài lớn hơn 1) theo cách chặt dần mắt xích của nó đem đi nối các đoạn xích khác, cho tới khi nó có độ dài là 1

    - Việc chặt-hàn dừng lại khi số đoạn xích chỉ còn 1

    Link download bài ví dụ: http://www.mediafire.com/download.php?hmwzyyz2xlw

    ~~~~~~~~~~~~~~

    Sample

    ~~~~~~~~~~~~~~

    var

    f: text;

    thoigian: word;

    somatxich: integer;

    matxich: array[1..20000] of integer;

    procedure input;

    var

    i: integer;

    begin

    assign(f,'noixich.inp';);

    reset(f);

    readln(f, somatxich);

    for i:=1 to somatxich do

    read(f, matxich[i]);

    close(f);

    end;

    procedure sort;

    var

    i, j, t: integer;

    begin

    for i:=1 to somatxich-1 do

    for j:=i+1 to somatxich do

    if matxich[i]>matxich[j] then

    begin

    t:=matxich[i];

    matxich[i]:=matxich[j];

    matxich[j]:=t;

    end;

    end;

    procedure calculate;

    var

    i: integer;

    begin

    sort;

    i:=1;

    thoigian:=0;

    while somatxich>1 do

    if matxich[i]+1<somatxich then

    begin

    somatxich:=somatxich-matxich[i]-1;

    thoigian:=thoigian+matxich[i]*2;

    i:=i+1;

    end

    else

    begin

    thoigian:=thoigian+(somatxich-1)*2;

    somatxich:=1;

    end;

    end;

    procedure output;

    begin

    assign(f, 'noixich.out';);

    rewrite(f);

    writeln(f, thoigian);

    close(f);

    end;

    begin

    input;

    calculate;

    output;

    end.

    Trả lời bởi Richmond
    ăm trước
    0 0
Những câu hỏi tương tự
Câu hỏi từ Thể loại Lập trình - Coding