Bài toán yêu cầu chúng ta xử lý dữ liệu về chiều cao của các cây phi lao và tính toán lượng gỗ thu hoạch.

Phân tích bài toán:

Chúng ta có một dãy các cây phi lao với chiều cao khác nhau. Ông Năm muốn thu hoạch một lượng gỗ nhất định (m mét) bằng cách cưa các cây ở một độ cao h nào đó. Phần gỗ thu hoạch được là phần ngọn của những cây cao hơn h. Mục tiêu là chọn h sao cho thu được ít nhất m mét gỗ và lượng gỗ dư ra là ít nhất.

Dữ liệu vào:

* Tệp \(PHILAO.INP\)
* Dòng 1: n (số lượng cây), m (lượng gỗ cần thu hoạch).
* Dòng 2: a1, a2, …, an (chiều cao các cây).

Yêu cầu:

a) Tính tổng lượng gỗ thu hoạch nếu cưa ở độ cao bằng cây thấp nhất.
b) Tìm độ cao cưa h hợp lí nhất để thu hoạch đủ m mét gỗ và lượng gỗ dư ra là ít nhất.

—

Phần a) Tính tổng số lượng mét gỗ thu hoạch được nếu chọn cưa hàng cây ở độ cao bằng với cây phi lao thấp nhất.

Bước 1: Xác định độ cao cưa.
Theo yêu cầu, chúng ta cần tìm cây phi lao thấp nhất. Đây là cây có chiều cao nhỏ nhất trong dãy \(a1, a2, …, an\).
Giả sử cây thấp nhất có chiều cao là \(min_height\). Khi đó, chúng ta sẽ cưa tất cả các cây ở độ cao \(min_height\).

Bước 2: Tính toán lượng gỗ thu hoạch.
Khi cưa ở độ cao \(min_height\), chỉ những cây có chiều cao lớn hơn \(min_height\) mới cho ta phần gỗ ở ngọn.
Đối với mỗi cây \(ai\):
* Nếu \(ai <= min_height\), cây này không cho gỗ vì nó đã bị cưa bằng hoặc thấp hơn gốc. * Nếu \(ai > min_height\), phần gỗ thu hoạch từ cây này sẽ là \(ai – min_height\).

Tổng lượng gỗ thu hoạch được sẽ là tổng của \((ai – min_height)\) cho tất cả các cây \(ai\) mà \(ai > min_height\).

Ví dụ minh họa:
Giả sử dãy chiều cao là: 20; 15; 10; 18.
Cây thấp nhất là 10 mét. Vậy \(min_height = 10\).
Chúng ta cưa ở độ cao 10 mét.

* Cây 1 (20m): Thu hoạch \(20 – 10 = 10\) mét gỗ.
* Cây 2 (15m): Thu hoạch \(15 – 10 = 5\) mét gỗ.
* Cây 3 (10m): Chiều cao bằng độ cao cưa, không thu hoạch gỗ.
* Cây 4 (18m): Thu hoạch \(18 – 10 = 8\) mét gỗ.

Tổng lượng gỗ thu hoạch được = 10 + 5 + 8 = 23 mét.

Thuật toán cho phần a):
1. Đọc n và m từ tệp \(PHILAO.INP\).
2. Đọc dãy chiều cao \(a1, a2, …, an\).
3. Tìm giá trị nhỏ nhất trong dãy \(a\) (gọi là \(min_height\)).
4. Khởi tạo biến \(total_wood_a = 0\).
5. Duyệt qua từng cây \(ai\) trong dãy \(a\):
Nếu \(ai > min_height\):
Cộng \((ai – min_height)\) vào \(total_wood_a\).
6. In \(total_wood_a\).

—

Phần b) Tìm vị trí h mét hợp lí nhất (h là số nguyên) sao cho thu hoạch được m mét gỗ và số mét gỗ dư ra là ít nhất.

Đây là phần phức tạp hơn. Chúng ta cần tìm một độ cao cưa \(h\) sao cho:
1. Tổng lượng gỗ thu hoạch được (tức là tổng \(ai – h\) cho các cây \(ai > h\)) phải lớn hơn hoặc bằng \(m\).
2. Lượng gỗ dư ra (tức là \((tổng gỗ thu hoạch) – m\)) là nhỏ nhất.

Bước 1: Phân tích mối quan hệ giữa h và lượng gỗ thu hoạch.
* Nếu ta tăng độ cao cưa \(h\), lượng gỗ thu hoạch được sẽ giảm.
* Nếu ta giảm độ cao cưa \(h\), lượng gỗ thu hoạch được sẽ tăng.

Điều này gợi ý rằng chúng ta có thể sử dụng phương pháp tìm kiếm nhị phân để tìm \(h\) một cách hiệu quả.

Bước 2: Xác định khoảng tìm kiếm cho h.
* Giá trị nhỏ nhất có thể của \(h\) là 0 (hoặc 1 theo đề bài là số nguyên dương). Tuy nhiên, nếu ta cưa ở độ cao 0, ta sẽ thu hoạch được toàn bộ chiều cao của các cây.
* Giá trị lớn nhất có thể của \(h\) là chiều cao của cây cao nhất. Nếu cưa ở độ cao này, ta sẽ không thu hoạch được gì.

Do đó, khoảng tìm kiếm cho \(h\) có thể là từ 0 (hoặc 1) đến \(max(a1, a2, …, an)\).

Bước 3: Xây dựng hàm kiểm tra (Check function).
Chúng ta cần một hàm để kiểm tra xem với một độ cao cưa \(h\) cho trước, ta có thu hoạch được ít nhất \(m\) mét gỗ hay không, và nếu có thì lượng gỗ dư ra là bao nhiêu.

Hàm \(calculate_harvest(h)\) sẽ trả về tổng lượng gỗ thu hoạch được nếu cưa ở độ cao \(h\).
\(calculate_harvest(h)\):
\(total_wood = 0\)
Duyệt qua từng cây \(ai\):
Nếu \(ai > h\):
\(total_wood = total_wood + (ai – h)\)
Trả về \(total_wood\)

Bước 4: Áp dụng tìm kiếm nhị phân.
Chúng ta sẽ tìm kiếm \(h\) trong khoảng \([low, high]\).
* \(low = 0\) (hoặc 1, tùy theo cách hiểu bài toán có cho phép cưa ở độ cao 0 hay không, nhưng vì \(a_i >= 1\) và \(h\) là số nguyên nên ta có thể coi \(low = 0\) để bao quát, hoặc \(low = 1\)).
* \(high = max(a1, a2, …, an)\) (hoặc một giá trị lớn hơn đủ để chắc chắn bao phủ mọi trường hợp, ví dụ như 10^9 + 7).

Quá trình tìm kiếm nhị phân:
1. Khởi tạo \(low = 0\), \(high = 1000000001\) (một giá trị lớn hơn max \(a_i\)), \(best_h = 0\), \(min_excess_wood = infinity\).
2. Trong khi \(low <= high\): a. Tính \(mid = low + (high - low) // 2\). b. Gọi hàm \(current_harvest = calculate_harvest(mid)\). c. Nếu \(current_harvest >= m\):
Điều này có nghĩa là \(mid\) có thể là một độ cao hợp lí. Chúng ta cần xem xét các độ cao thấp hơn để giảm lượng gỗ dư ra.
* Lượng gỗ dư ra: \(excess_wood = current_harvest – m\).
* Nếu \(excess_wood < min_excess_wood\): Cập nhật \(min_excess_wood = excess_wood\). Cập nhật \(best_h = mid\). * Tìm kiếm ở nửa dưới: \(high = mid - 1\). d. Nếu \(current_harvest < m\): Điều này có nghĩa là \(mid\) quá cao, không thu hoạch đủ gỗ. Chúng ta cần giảm độ cao cưa. * Tìm kiếm ở nửa trên: \(low = mid + 1\). Sau khi vòng lặp kết thúc, \(best_h\) sẽ là độ cao cưa hợp lí nhất để thu hoạch đủ m mét gỗ và lượng gỗ dư ra là ít nhất. Lưu ý quan trọng về thuật toán \(calculate_harvest(h)\):
Tính tổng \(ai – h\) cho tất cả \(ai > h\) có thể tốn thời gian nếu chúng ta duyệt lại toàn bộ mảng \(a\) mỗi lần gọi \(calculate_harvest\).
Để tối ưu, chúng ta có thể tiền xử lý.
Một cách để tối ưu là sắp xếp mảng \(a\) theo thứ tự tăng dần.
Khi mảng \(a\) đã được sắp xếp, việc tính \(calculate_harvest(h)\) sẽ nhanh hơn.
Giả sử \(a\) đã được sắp xếp: \(a1 <= a2 <= ... <= an\). Nếu ta cưa ở độ cao \(h\), tất cả các cây \(ai\) mà \(ai > h\) sẽ nằm ở phía sau của một chỉ số nào đó.
Chúng ta có thể tìm chỉ số \(k\) sao cho \(ak <= h < ak+1\) bằng cách sử dụng tìm kiếm nhị phân trên mảng đã sắp xếp. Khi đó, các cây cho gỗ là \(ak+1, ak+2, ..., an\). Tổng gỗ thu hoạch là: \((ak+1 - h) + (ak+2 - h) + ... + (an - h)\). Tổng này có thể tính bằng công thức: \((Tổng_từ_k+1_đến_n_của_ai) - (n - k) * h\). Để tính \(Tổng_từ_k+1_đến_n_của_ai\) hiệu quả, ta có thể dùng mảng tổng tiền tố. Đặt \(prefix_sum[i] = a1 + a2 + ... + ai\). Thì \(Tổng_từ_k+1_đến_n_của_ai = prefix_sum[n] - prefix_sum[k]\). Thuật toán chi tiết cho phần b) (sử dụng sắp xếp và tìm kiếm nhị phân):
1. Đọc n và m.
2. Đọc dãy chiều cao \(a\).
3. Sắp xếp mảng \(a\) theo thứ tự tăng dần.
4. Tính mảng tổng tiền tố \(prefix_sum\). \(prefix_sum[i] = a[1] + … + a[i]\). (Sử dụng chỉ số mảng từ 1 hoặc 0 tùy theo ngôn ngữ lập trình).
5. Xác định khoảng tìm kiếm cho \(h\): \(low = 0\), \(high = a[n]\) (hoặc 10^9+7).
6. Khởi tạo \(best_h = 0\), \(min_excess_wood = infinity\) (một giá trị rất lớn).
7. Trong khi \(low <= high\): a. \(mid = low + (high - low) // 2\). b. Tìm chỉ số \(k\) lớn nhất sao cho \(a[k] <= mid\) bằng tìm kiếm nhị phân trên mảng \(a\). (Nếu không có cây nào thỏa mãn, \(k = 0\)). c. Tính tổng gỗ thu hoạch \(current_harvest\): * Nếu \(k == n\) (tất cả cây đều nhỏ hơn hoặc bằng \(mid\)), \(current_harvest = 0\). * Nếu \(k < n\): Số lượng cây cho gỗ là \(num_trees_for_wood = n - k\). Tổng chiều cao của các cây cho gỗ là \(sum_height_for_wood = prefix_sum[n] - prefix_sum[k]\). \(current_harvest = sum_height_for_wood - num_trees_for_wood * mid\). d. Nếu \(current_harvest >= m\):
* \(excess_wood = current_harvest – m\).
* Nếu \(excess_wood < min_excess_wood\): \(min_excess_wood = excess_wood\). \(best_h = mid\). * Thử tìm \(h\) thấp hơn: \(high = mid - 1\). e. Nếu \(current_harvest < m\): * Cần giảm \(mid\), nên \(low = mid + 1\). 8. In \(best_h\). Ví dụ minh họa cho phần b):
Dãy chiều cao: 20, 15, 10, 18. Cần m = 7 mét gỗ.
Sắp xếp mảng \(a\): 10, 15, 18, 20.
\(n = 4\), \(m = 7\).
Tổng tiền tố: \(prefix_sum\) = [0, 10, 25, 43, 63] (nếu dùng chỉ số từ 1).
Khoảng tìm kiếm \(h\): [0, 20].

* \(low = 0\), \(high = 20\). \(mid = 10\).
\(a[k] <= 10\): \(k = 1\) (cây có chiều cao 10). Số cây cho gỗ: \(4 - 1 = 3\). Tổng chiều cao các cây cho gỗ: \(prefix_sum[4] - prefix_sum[1] = 63 - 10 = 53\). \(current_harvest = 53 - 3 * 10 = 23\). \(23 >= 7\). \(excess_wood = 23 – 7 = 16\).
\(min_excess_wood = 16\), \(best_h = 10\).
\(high = 10 – 1 = 9\).

* \(low = 0\), \(high = 9\). \(mid = 4\).
\(a[k] <= 4\): \(k = 0\). Số cây cho gỗ: \(4 - 0 = 4\). Tổng chiều cao: \(prefix_sum[4] - prefix_sum[0] = 63 - 0 = 63\). \(current_harvest = 63 - 4 * 4 = 47\). \(47 >= 7\). \(excess_wood = 47 – 7 = 40\).
\(40 > 16\), không cập nhật.
\(high = 4 – 1 = 3\).

* \(low = 0\), \(high = 3\). \(mid = 1\).
… (tương tự, ta sẽ thấy \(current_harvest\) lớn hơn \(m\) nhưng \(excess_wood\) có thể lớn hơn hoặc bằng 16).
… (Quá trình tìm kiếm sẽ tiếp diễn…)

Giả sử khi kiểm tra \(h = 15\):
\(mid = 15\).
\(a[k] <= 15\): \(k = 2\) (cây có chiều cao 15). Số cây cho gỗ: \(4 - 2 = 2\). Tổng chiều cao các cây cho gỗ: \(prefix_sum[4] - prefix_sum[2] = 63 - 25 = 38\). \(current_harvest = 38 - 2 * 15 = 38 - 30 = 8\). \(8 >= 7\). \(excess_wood = 8 – 7 = 1\).
\(1 < 16\). Cập nhật \(min_excess_wood = 1\), \(best_h = 15\). \(high = 15 - 1 = 14\). Sau khi vòng lặp kết thúc, \(best_h\) sẽ là 15. Cân nhắc về giới hạn dữ liệu:
\(n\) có thể lên tới 10^6, \(m\) tới 10^7, \(a_i\) tới 10^9.
* Phần a: Duyệt qua mảng \(a\) một lần, tốn O(n). Tìm min cũng O(n). OK.
* Phần b:
* Sắp xếp: O(n log n).
* Tính tổng tiền tố: O(n).
* Tìm kiếm nhị phân cho \(h\): Độ phức tạp là O(log(max_a)).
* Bên trong vòng lặp tìm kiếm nhị phân cho \(h\):
* Tìm chỉ số \(k\): O(log n) nếu dùng tìm kiếm nhị phân trên mảng \(a\) đã sắp xếp.
* Tính \(current_harvest\): O(1) nhờ mảng tổng tiền tố.
Tổng cộng cho phần b) là O(n log n + log(max_a) * log n). Với \(n = 10^6\), \(log n\) khoảng 20. \(log(max_a)\) khoảng 30. Độ phức tạp là chấp nhận được.

Hy vọng bài giải chi tiết này giúp các em hiểu rõ cách giải bài toán cây phi lao. Nếu có câu hỏi gì, đừng ngần ngại hỏi thầy nhé!