Tưới Nước Cho Rau
Đề bài
Nhà bạn Hùng có một luống rau thẳng dài $N$ mét, bạn lắp đặt $k$ vòi tưới tại các vị trí $V_1, V_2, \ldots, V_k$. Tính từ lúc bật: giây đầu tiên vị trí tại vòi được tưới, cứ sau 1 giây thì nước tại mỗi vòi chảy lan sang 1m hai bên. (Không tính 0.5s lan sang 0.5m).
Bạn đang thắc mắc với cách lắp đặt của mình thì cần bật các vòi nước tối thiểu bao lâu để mọi vị trí rau từ 1 đến $N$ đều được tưới. Dữ liệu đảm bảo $V[i-1] \lt V[i]$.
Dữ liệu nhập
- Dòng 1 là $N$ và $K$.
- Dòng 2 là dãy vị trí $V$.
Kết quả
- In ra thời gian tối thiểu $t$.
Ràng buộc
- $0 \lt K \le N \lt 1\,000\,000$
- $1 \le V[i] \le N$
2 1
228 3
2 6 73Giải thích ví dụ 1: $N = 2$, $k = 1$: một vòi nước duy nhất lắp đặt tại vị trí 2 thì sau đúng 2s mới lan sang hết vị trí 1.
Giải thích ví dụ 2: luống rau dài $N = 8$. Có $k = 3$ vòi nước lắp đặt như sau:
Sau 3 giây thì tại vị trí 4 mới được tưới nước.
Lờ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 CodeforcesHiểu đề qua 2 test ví dụ
Bài này thì bạn học viên của mình gặp khó khăn ngay từ bước đọc hiểu đề, nên mình sẽ giải thích rõ 2 test ví dụ để bạn nào có không hiểu vì sao ra được như vậy thì sẽ rõ ràng, từ đó làm cơ sở giải quyết.
Các bạn đọc kỹ đề hen, ngay tại giây đầu tiên (giây thứ 1) thì nước sẽ chảy ra tại vị trí đặt các vòi. Sau đó tại mỗi vị trí vòi thì nước sẽ lan ra vị trí lân cận 2 bên (đề bài chỗ này nói 1m của 2 bên thì hơi khó hiểu, nên nói rõ là mỗi vị trí lân cận 2 bên), cứ mỗi giây sẽ lan ra đồng thời vị trí lân cận ở cả 2 phía. Như thế này cho các bạn dễ hình dung: ví dụ ta có chiều dài $N = 5$, nghĩa là có 5 vị trí (1, 2, 3, 4, 5), và có 1 vòi nước duy nhất tại vị trí 3. Như vậy giây đầu tiên nước sẽ chảy ra tại vị trí 3 (là vị trí đặt vòi nước). Rồi 1 giây tiếp theo, tức là tại giây thứ 2, thì nước sẽ lan ra 2 vị trí lân cận là 2, 4. Rồi tại giây thứ 3 thì nước sẽ lan ra 2 vị trí lân cận tiếp theo là 1, 5. Như thế sau 3 giây là nước sẽ lan ra hết $N = 5$ vị trí.
Thì các bạn nhìn vào test ví dụ 1: khi ta có $N = 2$, tức là có 2 vị trí 1, 2 và vòi nước đặt tại vị trí 2. Như thế thì giây đầu tiên nước chảy ra tại vòi, giây thứ 2 nước sẽ chảy lan sang vị trí 1 (ở bài này do chỉ có 2 vị trí nên ta không tính việc nó sẽ chảy sang vị trí 3). Như thế chỉ cần 2 giây là toàn bộ đều sẽ được tưới nước nên output là 2.
Tiếp tục ở test ví dụ 2: có $N = 8$ vị trí (1, 2, 3, 4, 5, 6, 7, 8) và vòi nước đặt tại các vị trí 2, 6, 7. Thì giây thứ 1 nước sẽ chảy tại các vị trí {2}, {6}, {7}. Mình cố tình dùng ký hiệu { } để bọc lại vị trí nước sẽ lan của từng vòi cho các bạn dễ nhìn. Sang giây thứ 2 thì vị trí nước tại các vòi sẽ lan như sau: {1, 3}, {5, 7}, {6, 8}. Lúc này vẫn còn vị trí 4 nước chưa lan tới. Nên tiếp tục sang giây thứ 3 thì vị trí nước tại các vòi sẽ lan như sau: {4}, {4, 8}, {5}. Lúc này đây vị trí 4 đã được lan tới, nghĩa là toàn bộ $N = 8$ vị trí đã được tưới nước, kết quả là sau 3 giây nên output là 3.
Bảng dưới đây mô phỏng lại test ví dụ 2 (ô xanh đậm là ô vừa được tưới ở giây đó):
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| Giây 1 | 🚰 | 🚰 | 🚰 | |||||
| Giây 2 | 💧 | 🚰 | 💧 | 💧 | 🚰 | 🚰 | 💧 | |
| Giây 3 | 💧 | 🚰 | 💧 | 💧 | 💧 | 🚰 | 🚰 | 💧 |
Vậy bây giờ đề bài đưa ra có tối đa gần $10^6$ vị trí cần tưới nước và có $K \le N$ vị trí đặt vòi nước, với từng vị trí đặt vòi đảm bảo luôn nằm trong đoạn từ 1 đến $N$. Hãy tính toán xem cần tối thiểu bao nhiêu giây để toàn bộ các vị trí đều được tưới nước?
Phân tích: chỉ cần quan tâm 2 vòi kề nhau
Đề bài có nói câu: sau 1 giây thì nước tại mỗi vòi sẽ lan sang đều 1m (hiểu là 1 vị trí) của 2 bên, qua đó có thể thấy tốc độ nước chảy ra tại mỗi vòi đều có công suất như nhau. Nếu là như vậy thì các bạn có thể hình dung điều sau đây, các bạn xem hình minh họa dưới đây:
Giả sử A, B, C, D là vị trí các vòi, S hiểu là Start, tức là vị trí đầu tiên cần tưới, và F hiểu là Finish, tức là vị trí cuối cùng cần tưới. Nếu xem công suất chảy nước tại mỗi vòi đều bằng nhau, vậy có phải nếu nước chảy từ vòi A lan sang bên trái sẽ tưới được hết đến vị trí S chắc chắn nhanh hơn nước chảy từ vòi B đúng không các bạn? Bởi lúc này SA < SB mà công suất chảy như nhau nên thằng nào ngắn hơn thì thằng đó sẽ nhanh hơn. Các bạn cũng có thể tưởng tượng 2 vận động viên chạy xe đạp có tốc độ như nhau, 1 người xuất phát từ A, 1 người xuất phát từ B, cả 2 cùng mục tiêu chạy đến đích S. Thì chắc chắn người xuất phát từ A sẽ đến đích sớm hơn. Vậy nên trong trường hợp này chỉ cần quan tâm mất bao lâu để nước từ vòi A chạm đến S chứ không cần quan tâm đến vòi B, tương tự là C, D, bởi rõ ràng SA < SB < SC < SD.
Tiếp tục, ta muốn lấp đầy đoạn AB thì có thể là nước chảy từ vòi A lan sang phải đến B, hoặc nước chảy từ vòi B lan sang trái đến A. Và rõ ràng đồng thời cả 2 vòi cùng chảy thì tốc độ lấp đoạn AB sẽ càng được rút ngắn lại. Tưởng tượng A = 2, B = 5. Nếu chỉ nước từ A chảy đến B thì phải cần 4 giây (giây thứ 1 tại A = 2, giây thứ 2 là vị trí 3, giây thứ 3 là vị trí 4, giây thứ 4 là vị trí B = 5), ngược lại cũng vậy. Nhưng nếu đồng thời cả 2 vòi cùng chảy thì giây thứ 1 nước chảy tại vị trí 2 và 5, giây thứ 2 nước chảy tại vị trí 3 và 4. Như vậy chỉ cần 2 giây là toàn bộ đoạn AB đã được tưới hết. Còn nước từ vòi C cũng lan qua trái đến B rồi đến A được, nhưng rõ ràng như thế mất nhiều thời gian hơn vì C đứng sau B, muốn lấp đoạn AB thì chỉ cần phối hợp vòi A và vòi B thôi đúng không các bạn?
Bước 2: từ vòi A lan sang phải, từ vòi B lan sang trái để lấp đoạn AB.
Bước 3: từ vòi B lan sang phải, từ vòi C lan sang trái để lấp đoạn BC.
Bước 4: từ vòi C lan sang phải, từ vòi D lan sang trái để lấp đoạn CD.
Bước 5: từ vòi D lan sang phải đến F để lấp đoạn DF.
Kết quả là thời gian lớn nhất trong 5 bước.
Ví dụ bước 1 cần 2 giây, bước 2 cần 3 giây, bước 3 cần 1 giây, bước 4 cần 5 giây, bước 5 cần 4 giây. Vậy rõ ràng khi tất cả cùng làm đồng thời thì thằng lớn nhất sẽ là thằng hoàn tất sau cùng, và khi đó tất cả đều được tưới hết ⇒ sẽ cần 5 giây.
Tìm công thức cho từng đoạn
Từ vòi đầu đến điểm đầu: như trong ví dụ trên là từ A đến S. Giây đầu tiên nước chảy tại A, sau đó mỗi giây lan ra 1 vị trí và cứ thế đến S. Giả sử A = 4, giây đầu tiên chảy tại vị trí 4, và vị trí 4 cách vị trí đầu tiên (là vị trí 1) là 3 khoảng cách, như thế sẽ cần thêm 3 giây ⇒ tổng lại 1 + 3 = 4 giây. Hay nếu A = 7 thì sẽ cần 7 giây, A = 10 sẽ cần 10 giây, A = 1 (ngay vị trí đầu tiên) thì cũng cần 1 giây, vẫn đúng. Vậy thời gian cần đúng bằng vị trí vòi đầu tiên luôn.
Từ vòi cuối đến điểm cuối: ví dụ $N = 10$, vòi cuối cùng tại vị trí 6. Giây đầu tiên chảy tại vị trí 6, khoảng cách còn lại là các vị trí 7, 8, 9, 10, tức là 4 vị trí ⇒ cần 4 giây nữa, cộng với 1 giây đầu tiên ⇒ cần 5 giây. Vậy công thức chính là: 1 + N − vị trí vòi cuối. Cụ thể 1 + 10 − 6 = 5. Thử kiểm tra nếu vòi cuối đặt tại 8 ⇒ 1 + 10 − 8 = 3 giây; nếu vòi cuối đặt tại N = 10 luôn ⇒ 1 + 10 − 10 = 1 giây, tức là nước chảy ra ngay tại vòi, vẫn đúng hen các bạn.
Giữa 2 vòi kề nhau: hãy thử qua vài ví dụ và nháp tay ra kết quả để chúng ta nhìn ra quy luật tổng quát:
| Hai vòi | Quãng đường B − A + 1 | Chia 2 | Số giây (làm tròn lên) |
|---|---|---|---|
| A = 2, B = 3 | 2 | 2/2 = 1 | 1 |
| A = 2, B = 4 | 3 | 3/2 = 1.5 | 2 |
| A = 2, B = 5 | 4 | 4/2 = 2 | 2 |
| A = 2, B = 6 | 5 | 5/2 = 2.5 | 3 |
| A = 2, B = 7 | 6 | 6/2 = 3 | 3 |
| A = 2, B = 8 | 7 | 7/2 = 3.5 | 4 |
Các bạn có nhìn ra vấn đề không? Ở vòi đầu tiên và vòi cuối cùng thì chỉ có 1 mình nó chảy, nhưng giờ đây cả 2 vòi cùng chảy ngược hướng và sẽ chạm nhau. Nếu từ A = 2 muốn đi đến B = 7 thì quãng đường cần chảy là 2, 3, 4, 5, 6, 7 ⇒ 6 vị trí (tính nhanh bằng B − A + 1 = 7 − 2 + 1 = 6). Bình thường nếu chỉ chảy từ A đến B sẽ cần 6 giây, nhưng do 2 vòi chảy từ 2 phía ngược nhau với tốc độ bằng nhau nên mỗi vòi chỉ cần chảy 1 nửa quãng đường là sẽ chạm tới nhau, tức là 6 / 2 = 3 giây là được. Tuy nhiên với A = 2, B = 6 ⇒ quãng đường là 5, lấy 5 / 2 = 2.5 giây; mà đề bài nói là không tính 0.5 giây mà chỉ tính chẵn 1 giây, nên 2.5 làm tròn lên thành 3 giây nhé các bạn.
Em nhập độ dài luống $N$ và vị trí các vòi rồi bấm Tiếp để xem nước lan từng giây. Bước cuối sẽ hiện thời gian của từng đoạn (đầu luống, giữa 2 vòi kề nhau, cuối luống) để em đối chiếu với công thức:
Code: lưu vị trí các vòi vào mảng – O(K)
Rồi vậy thì công thức giải quyết cho bài này giờ đây rất đơn giản: ta lưu trữ các vị trí các vòi vào mảng a (đề đã đảm bảo sắp theo thứ tự tăng dần). Khởi tạo Max = giá trị lớn nhất giữa a[0] (thời gian vòi đầu tiên chảy đến điểm đầu của ruộng) và 1 + n - a[k - 1] (thời gian vòi cuối cùng chảy đến vị trí cuối cùng của ruộng). Rồi vòng lặp bắt đầu xét từ phần tử thứ 2 trong mảng, gọi đó là a[i], ta tính thời gian giữa a[i] và a[i - 1] bằng cách làm tròn lên (a[i] - a[i - 1] + 1) / 2, rồi so sánh cập nhật lại Max, cứ thế lặp đến hết vòi cuối cùng. Sau cùng in ra Max chính là thời gian ít nhất để toàn bộ ruộng được tưới.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 5;
int a[MAX];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for(int i = 0; i < k; ++i){
cin >> a[i];
}
int Max = max(a[0], 1 + n - a[k - 1]);
for(int i = 1; i < k; ++i){
Max = max(Max, (int)ceil((a[i] - a[i - 1] + 1) / 2.0));
}
cout << Max;
return 0;
}import math
n, k = map(int, input().split())
a = list(map(int, input().split()))
Max = max(a[0], 1 + n - a[-1])
for i in range(1, k):
Max = max(Max, math.ceil((a[i] - a[i - 1] + 1) / 2))
print(Max)Giải thích một số chỗ trong code ở trên:
1/ 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, như trường hợp bài này phần input có thể lên đến gần 1 triệu số cần nhập, thì ta nên để thêm 2 dòng này vào đầu để chương trình 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é.
2/ Chỗ tính toán trong vòng lặp, phép chia các bạn phải để chia cho 2.0 để nó hiểu phép chia đó là phép chia ra kết quả thực nhé. Do mảng a là mảng số nguyên nên a[i] - a[i - 1] + 1 ra kết quả số nguyên, nếu chia cho 2 thì 2 cũng là số nguyên, từ đó phép chia đó là dạng số nguyên / số nguyên thì kết quả sẽ ra số nguyên và sẽ bị sai nha các bạn. Ví dụ lúc này sẽ là 5 / 2 thì kết quả chỉ ra 2, từ đó hàm ceil làm tròn lên cũng chỉ là 2, thì rõ ràng là sai vì đúng phải ra 5 / 2 = 2.5, từ đó hàm ceil làm tròn lên 3. Nên ta để chia cho 2.0 ý cho compiler biết số 2 đó ở định dạng số thực. Chỉ cần tử số hay mẫu số có kiểu số thực thì compiler sẽ cho ra kết quả chia số thực. Hàm ceil nằm trong thư viện toán học, do ta đã dùng thư viện bits/stdc++.h bao chứa các thư viện khác nên không cần include riêng, nhưng nếu không dùng thư viện này thì các bạn nhớ include thư viện cmath vào thì mới sử dụng hàm ceil được nhé.
(x + 1) / 2 thay cho ceil(x / 2.0). Với bài này là (a[i] - a[i - 1] + 2) / 2, kết quả y hệt.Đánh giá độ phức tạp của cách làm này:
- Độ phức tạp không gian (Space Complexity): $O(K)$ do ta dùng mảng
acó $K$ phần tử để lưu trữ vị trí các vòi nước. - Độ phức tạp thời gian (Time Complexity): $O(K)$ của bước đọc vị trí các vòi nước vào mảng + $O(K)$ của bước duyệt mảng để tính thời gian chảy giữa 2 vòi. Nên tổng sẽ là $O(2K)$, theo quy tắc BigO khi nhân với hằng số ta có thể bỏ qua, vì thế có thể kết luận tổng quát là $O(K)$.
Với $K$ tối đa gần $10^6$ thì $2K$ khoảng $2 \cdot 10^6$, yên tâm sẽ không bị TLE nha các bạn, vì như hồi đầu bài mình có nói nếu tổng số lần lặp $\le (3 \text{ đến } 5) \cdot 10^7$ là chắc ăn rồi. Mình chạy thử với $N = K = 999\,999$ thì bản C++ chỉ khoảng 0.05 giây, bản Python khoảng 0.4 giây.
Vậy đến đây nhìn lại ta sẽ thấy bài này chỉ là bài tập cơ bản về mảng 1 chiều thôi. Bản chất trên trang web cũng liệt kê bài tập này thuộc về thể loại mảng 1 chiều.
Tối ưu thêm: không cần mảng – bộ nhớ O(1)
Tuy nhiên mình muốn đem đến một góc nhìn khác cho các bạn, tối ưu hơn cho bài này. Bài này vẫn theo hướng giải quyết như đã trình bày nhưng ta không cần sử dụng mảng, tức là độ phức tạp bộ nhớ chỉ là $O(1)$ hằng số nha các bạn, và ta có thể kết hợp cả quá trình đọc dữ liệu và quá trình xử lý trong duy nhất 1 vòng lặp. Tức là độ phức tạp về mặt lý thuyết vẫn là $O(K)$, nhưng thực tế thì tốt hơn code trước vì chỉ cần 1 lần lặp duy nhất thôi.
Ta sẽ dùng biến x đọc dữ liệu từng số từ input vào, đồng thời có biến temp_x: trước khi x nhận giá trị mới từ input thì temp_x sẽ lưu lại giá trị x hiện tại, sau đó x nhận giá trị mới, rồi đi tính thời gian giữa temp_x và x.
Xem code tối ưu bộ nhớ O(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k, x, temp_x;
cin >> n >> k;
cin >> x;
int Max = x;
while(--k){
temp_x = x;
cin >> x;
Max = max(Max, (int)ceil((x - temp_x + 1) / 2.0));
}
cout << max(Max, 1 + n - x);
return 0;
}Trước khi vào vòng lặp mình chủ động cin >> x; để đọc giá trị x đầu tiên từ input, từ đó gán Max = x vì đó cũng là thời gian nước chảy từ vòi đầu tiên đến vị trí đầu tiên của ruộng. Và khi đã đọc trước 1 giá trị thì số lần lặp tiếp theo chỉ còn $k - 1$ lần, vì thế mình để while(--k), nghĩa là giảm $k$ đi 1 đơn vị trước rồi sau đó kiểm tra nếu $k$ khác 0 thì vòng lặp tiếp tục, nếu $k$ bằng 0 thì vòng lặp kết thúc. Rồi cứ thế gán temp_x = x, nhập giá trị x mới rồi tính toán cập nhật lại Max. Sau cùng thì xuất ra số lớn nhất giữa Max và thời gian từ vòi cuối cùng đến vị trí cuối cùng của ruộng.
Mình đã kiểm tra cả 3 bản code với 500 bộ test ngẫu nhiên, so với cách mô phỏng từng giây, đều cho cùng kết quả.
Nhận xét
Đăng nhận xét