Chặt Cây Xây Nhà
Đề bài
Bob là 1 thợ mộc tài hoa. Hiện tại anh đang có kế hoạch xây dựng một căn nhà toàn bộ bằng gỗ. Biệt thự được xây bởi các khúc gỗ khác nhau và tổng độ dài của các thanh gỗ là $L$.
Để lấy các khúc gỗ đó, anh ấy cần vào rừng và chặt cây. Khu rừng gần chỗ anh có $N$ cây với độ cao khác nhau. Bob sẽ dùng một cái máy cưa đặc biệt, nó có thể cắt một lượt qua tất cả các cây.
Đầu tiên, anh ấy sẽ chọn một độ cao cố định là $H$, sau đó dùng máy cưa đặc biệt để cắt một đường theo độ cao $H$ này trên các cây có độ cao lớn hơn $H$.
Ví dụ: các cây có độ cao lần lượt là 10, 16, 17, 15. Chọn $H = 15$. Do đó, cây thứ 2, 3 sẽ được cắt và tổng độ dài các khúc gỗ thu được là $1 + 2 = 3$.
Cho độ cao của các cây trong rừng và giá trị $L$ (tổng độ dài của các khúc gỗ cần). Hãy giúp Bob tìm giá trị lớn nhất của $H$ thoả mãn rằng Bob chỉ cần dùng máy cắt đúng một lượt để thu được số các khúc gỗ cần thiết.
Chú ý: tổng độ dài các khúc gỗ thoả mãn có thể lớn hơn $L$ (hay nói cách khác $L \le$ tổng độ dài).
Input: dòng đầu tiên chứa một số nguyên mô tả số lượng cây $N$ $(1 \le N \le 10^6)$ và $L$ là tổng độ dài của các khúc gỗ cần dùng $(1 \le L \le 2 \cdot 10^9)$. Dòng tiếp theo là độ cao tương ứng của các cây $h[i]$ $(h[i] < 10^9)$. Tổng độ cao của các cây lớn hơn hoặc bằng $L$.
Output: dòng duy nhất gồm 1 số nguyên duy nhất: giá trị độ cao lớn nhất mà tại đó Bob cắt đúng một đường để thu được các khúc gỗ thoả mãn.
Giới hạn
- 50% số test đầu tiên có $h[i] \le 10^3$, $N \le 10^3$.
- 50% số test còn lại không có giới hạn gì thêm.
3 6
1 2 304 10
10 15 12 13104 1
5 5 5 54Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Hiểu đềTóm tắt đề bài
Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau: cho $N$ cây gỗ, $L$ là tổng độ dài các khúc gỗ cần dùng, mảng $h$ gồm $N$ phần tử với $h[i]$ là độ cao của cây thứ $i$. Ta có chiếc máy cưa đặc biệt: khi chọn 1 độ cao cố định $H$, nó lướt qua tất cả các cây, và những cây có độ cao $> H$ sẽ cho $h[i] - H$ khúc gỗ.
Ví dụ: $N = 4$, $L = 10$, $h = \{10, 15, 12, 13\}$. Thì $H$ lớn nhất ta tìm được sẽ bằng 10: cây thứ nhất có $h[1] \le H$ nên không thu được gỗ, cây thứ 2 thu được $15 - 10 = 5$, cây thứ 3 thu được $12 - 10 = 2$, cây thứ 4 thu được $13 - 10 = 3$. Tổng cộng $5 + 2 + 3 = 10$ khúc gỗ, thoả mãn $\ge L$.
Em tự tay kéo thanh trượt $H$ dưới đây để thấy máy cưa "lướt" qua các cây như thế nào nhé. Phần màu cam phía trên đường cưa chính là gỗ thu được:
50%Cách vét cạn: thử H từ trên xuống
Giờ cách làm đơn giản nhất của bài này là vét cạn thôi. Ta chắc chắn rằng $H$ sẽ nằm trong khoảng từ 0 đến độ cao cây gỗ cao nhất trừ 1 (ta gọi là hMax - 1 nha). Nhiều bạn sẽ nghĩ tới việc cho $H$ chạy từ 0 lên hMax - 1, nhưng bởi vì ta đang cần tìm $H$ lớn nhất, tại sao ta không thử chạy ngược lại, từ hMax - 1 về 0? Khi đó, lần đầu tiên ta gặp một giá trị thoả mãn số gỗ $\ge L$ là ta kết luận luôn đó là $H$ lớn nhất rồi.
Ví dụ $N = 4$, $L = 10$, $h = \{10, 15, 12, 13\}$, $hMax = 15$, ta cho $H$ chạy từ 14 về 0:
| H | Số gỗ thu được | So với L = 10 |
|---|---|---|
| 14 | 1 = 1 | ✘ nhỏ hơn L |
| 13 | 2 = 2 | ✘ nhỏ hơn L |
| 12 | 3 + 1 = 4 | ✘ nhỏ hơn L |
| 11 | 4 + 1 + 2 = 7 | ✘ nhỏ hơn L |
| 10 | 5 + 2 + 3 = 10 | ✔ ≥ L, chọn! |
Em nhập $L$ và độ cao các cây rồi bấm Tiếp để xem cách vét cạn hạ dần đường cưa $H$ từ cây cao nhất xuống, tới lần đầu tiên thu đủ gỗ thì dừng:
Mặc dù về độ phức tạp thời gian thì chạy từ trên xuống hay từ dưới lên là như nhau, nhưng ta chọn chạy từ trên xuống vì chỉ cần gặp trường hợp đầu tiên thoả mãn thì kết luận được ngay.
Đây là source code cho bạn nào muốn tham khảo cách làm trên của mình nha:
Xem code vét cạn (50% điểm)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll N, L;
cin >> N >> L;
vector<ll> h(N);
ll hMax = 0;
for(int i = 0; i < N; ++i) {
cin >> h[i];
hMax = max(hMax, h[i]);
}
for(int H = hMax; H >= 0; --H) {
ll sum = 0;
for(int i = 0; i < N; ++i) {
if(h[i] > H) {
sum += h[i] - H;
}
}
if(sum >= L) {
cout << H;
break;
}
}
return 0;
}N, L = map(int, input().split())
h = list(map(int, input().split()))
hMax = max(h)
for H in range(hMax, -1, -1):
s = 0
for x in h:
if x > H:
s += x - H
if s >= L:
print(H)
breakGiải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều, ví dụ như bài này dữ liệu đầu vào có thể lên đến $10^6$ số, thì ta hãy nên để 2 dòng này vào để chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.vector<ll> h(N): ta khai báo vector $h$ có $N$ phần tử để tiện việc đọc, chỉ việccin >> h[i].
Ta dễ dàng nhận thấy cách trên không thể nào AC được. Trong trường hợp xấu nhất $hMax = 10^9$, $N = 10^6$, và muốn chặt hết toàn bộ các cây ta cần chặt tận gốc, $H = 0$ chẳng hạn, thì sẽ chạy tận $10^9 \times 10^6 = 10^{15}$ phép tính. Thời gian cần lên tới $10^{15} / 10^8 = 10^7$ giây, 10 triệu giây là tầm hơn 100 ngày đó 😱.
Tuy nhiên hãy vẫn nên cài đặt nó để sau này lấy làm công cụ kiểm tra tính chính xác cho cách làm tối ưu. Bạn nào chưa biết cách lấy nó làm công cụ kiểm tra thì xem bài viết Hạn chế lỗi Wrong Answer của mình nha.
Ghi chú viết tắt: AC (Accepted – được chấp thuận), TLE (Time Limit Exceeded – quá thời gian), WA (Wrong Answer – sai kết quả).
100%Cách tối ưu: chặt nhị phân kết quả
Để AC bài này ta dùng giải thuật tìm kiếm nhị phân trên kết quả (còn gọi là chặt nhị phân kết quả, hay gọi tắt là chặt nhị phân). Để áp dụng được, ta cần thoả mãn 3 điều sau:
Ví dụ $N = 4$, $L = 13$, $h = \{10, 15, 12, 13\}$. Bảng dưới là số gỗ thu được với từng giá trị $H$:
- Thử $H = 7$: số gỗ $= 22 \ge L$, thoả mãn. Mọi giá trị $H \le 7$ chắc chắn cũng thoả mãn, vì H càng xuống thì gỗ thu được càng nhiều. Còn $H > 7$ thì chưa biết, có thể đáp án là 7, cũng có thể đáp án nằm ở phía $H > 7$.
- Thử $H = 11$: số gỗ $= 7 < L$, không thoả mãn. Mọi giá trị $H \ge 11$ chắc chắn cũng không thoả mãn, vì H càng cao thì gỗ thu được càng giảm.
- Vậy $H$ lớn nhất có khả năng nằm trong $8 \le H \le 10$, nếu không thì sẽ là 7. Thử $H = 9$: số gỗ $= 14$, thoả mãn. Đáp án không phải 7 nữa, mà có thể là 9 hoặc 10.
- Thử $H = 10$: số gỗ $= 10$, không thoả mãn. Vậy $H$ lớn nhất bằng 9.
Các bước thực hiện
- Ba biến
left,right,res: đoạn $[left, right]$ là khoảng mà $H$ lớn nhất có khả năng nằm trong đó, cònreslưu kết quả tốt nhất đã biết. Lúc đầures = 0(chắc chắn thoả mãn vì tổng độ cao các cây $\ge L$),left = 1,right = hMax - 1. - Hàm
check(H): trả vềtruenếu với độ cao $H$ ta thu được lượng gỗ $\ge L$. - Biến
mid = (left + right) / 2: nếucheck(mid)sai thì mọi $H \ge mid$ đều sai, cập nhậtright = mid - 1. Nếu đúng thì mọi $H \le mid$ đều đúng, cập nhậtres = midvàleft = mid + 1. Lặp lại đến khileft > rightthì dừng và in rares.
Bạn nhìn lại ví dụ ở trên đi, mình chọn các giá trị thử dựa đúng theo mid = (left + right) / 2 đó:
| [left, right] | mid | gỗ khi H = mid | check(mid) | Cập nhật | res |
|---|---|---|---|---|---|
| [1, 14] | 7 | 22 | true | res = 7, left = 8 | 7 |
| [8, 14] | 11 | 7 | false | right = 10 | 7 |
| [8, 10] | 9 | 14 | true | res = 9, left = 10 | 9 |
| [10, 10] | 10 | 10 | false | right = 9 | 9 |
Giờ em tự tay chạy từng bước nhé. Có thể sửa $L$ và độ cao các cây để thử với dữ liệu của mình:
Đây là source code cho bạn nào muốn tham khảo cách làm trên của mình:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll N, L;
vector<ll> h;
bool check(ll H) {
ll sum = 0;
for(int i = 0; i < N; ++i) {
if(h[i] > H) {
sum += h[i] - H;
}
}
return sum >= L;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> L;
ll hMax = 0;
for(int i = 0; i < N; ++i) {
ll x;
cin >> x;
hMax = max(hMax, x);
h.push_back(x);
}
ll res = 0, left = 1, right = hMax - 1;
while(left <= right) {
ll mid = (left + right) / 2;
if(check(mid)) {
res = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
cout << res;
return 0;
}import sys
from bisect import bisect_right
def main():
data = sys.stdin.buffer.read().split()
N, L = int(data[0]), int(data[1])
h = sorted(map(int, data[2:2 + N]))
# suffix[i] = tổng các h[j] với j >= i (mảng đã sắp xếp tăng dần)
suffix = [0] * (N + 1)
for i in range(N - 1, -1, -1):
suffix[i] = suffix[i + 1] + h[i]
def check(H):
i = bisect_right(h, H) # các cây từ vị trí i trở đi cao hơn H
return suffix[i] - H * (N - i) >= L
res, left, right = 0, 1, h[-1] - 1
while left <= right:
mid = (left + right) // 2
if check(mid):
res = mid
left = mid + 1
else:
right = mid - 1
print(res)
main()Giải thích một số chỗ trong code
return sum >= L;: nếu sum >= L thì hàm trả về true, ngược lại là false thôi nha.
Hàm check mất $O(N)$ phép tính, còn vòng lặp while chỉ chạy $\log_2(hMax)$ lần. Trường hợp xấu nhất chỉ phải thực hiện $10^6 \times \log_2(10^9) \approx 3 \cdot 10^7$ phép tính, tầm 0.3 giây, nhanh hơn cách vét cạn rất nhiều rồi đúng không các bạn?
check(H) chỉ cần tìm nhị phân vị trí cây đầu tiên cao hơn $H$ (bisect) thay vì duyệt cả mảng. Ý tưởng chặt nhị phân trên $H$ vẫn giữ nguyên. Cả 4 bản code đã được kiểm tra với 400 bộ test ngẫu nhiên so với cách vét cạn; với $N = 10^6$, bản C++ chạy khoảng 0.15 giây, bản Python khoảng 1 giây.
Nhận xét
Đăng nhận xét