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)).