Bài viết sưu tầm

Bài  toán Cưa gỗ

Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có N cây, mỗi cây có độ cao là a₁, a₂,…a_N.

Người  ta  cần  lấy  M  mét  gỗ  bằng  cách  đặt  cưa  máy  sao  cho lưỡi cưa  ở  độ  cao H (mét) để  cưa tất cả  các cây có độ  cao lớn hơn H (dĩ nhiên những cây có độ cao không lớn hơn H thì không bị cưa).

Ví dụ: Nếu hàng cây có các cây với độ  cao  tương  ứng là 20; 15; 10 và 18 mét, cần lấy 7 mét gỗ. Lưỡi cưa đặt tại độ cao hợp lí là 15 mét thì độ  cao của các cây còn lại sau khi bị cưa tương ứng là 15; 15; 10 và 15 mét. Tổng số  mét gỗ  lấy được là 8 mét (dư 1 mét).

Yêu  cầu:  Hãy  tìm  vị  trí  đặt  lưỡi  cưa  hợp  lí  (số  nguyên  H lớn nhất) sao cho lấy được M mét gỗ  và số  mét gỗ  dư ra là ít nhất.

Dữ liệu vào:Đọc từ file văn bản WOOD.INP có cấu trúc

- Dòng  thứ  nhất  chứa  2  số  nguyên  dương  N  và  M  (1≤N≤10⁶; 1≤M≤2.10⁹) cách nhau một dấu cách.

- Dòng thứ  hai chứa N số  nguyên dương ai là độ  cao của mỗi cây trong hàng (1≤a_i≤10⁹; i=1…N), mỗi số  cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file WOOD.OUT, một dòng duy nhất ghi một số nguyên cho biết giá trị cần tìm.

Ví dụ:

Hướng dẫn:

Gọi Max là giá trị lớn nhất của hàng cây.

Cách 1:

Duyệt vị trí đặt lưỡi cưa từ Max về 0, Nếu thỏa mãn thì lấy vị trí và kết thúc.

Function IsOk(h:Longint):Boolean;

Var i:Longint;

Begin

S:=0;

For i:=1 To N Do

If A[i]>h Then S:=S+A[i]-h;

Exit(S>=M);

End;

Function Wood:Longint;

Begin

For h:=Max Downto 0 Do

If IsOK(h) Then Exit(h);

End;

Độ phức tạp là O(N.Max).

Cách 2:

Tìm kiếm nhị phân theo độ cao cần đặt lưỡi cưa như sau:

d=0, c= Max,

Lặp khi d ≤ c.

h=(d+c) Div 2

Kiểm  tra  số  mét  gỗ  được lấy ra khi  chặt  ở  độ  cao h có thỏa không?

- Nếu thỏa Thì tìm kiếm nhị phân h từ d=h đến c.

- Ngược lại thì tìm kiếm nhị phân h từ d đến c=h-1

Function Wood:Longint;

Begin

d:=0;c:=Max;

While d ≤ c Do

Begin

h:=(d+c) Div 2;

If IsOK(h) Then d:=h

Else c:=h-1;

End;

Exit(h);

End;

Độ phức tạp là O(N.Log(Max)).