Dự Trữ Nước
Đề bài
Ở miền Trung thường năm nào cũng có những đợt hạn hán nên ông Nam có những thùng dự trữ nước. Do mua làm nhiều đợt nên $N$ $(1 \le N \le 10^6)$ thùng chứa nước của ông Nam có kích thước khác nhau, mỗi thùng có sức chứa $C_i$ $(1 \le C_i \le 10^7,\ 1 \le i \le N)$.
Dự đoán rằng năm nay sẽ có đợt hạn hán lớn nên ông Nam muốn đổ đầy nước hết các thùng để dự trữ. Sau khi kiểm tra ông Nam thấy rằng có một số thùng vẫn còn đầy, một số khác thì vơi đi một phần, còn một số thì đã hết. Ông quyết định các thùng nào chưa đầy thì sẽ chở đi để đổ đầy nước. Nhưng do nơi lấy nước rất xa, và mỗi lần chỉ chở đi được 1 thùng, và mỗi thùng chỉ được chở đi một lần nên ông quyết định sẽ san nước giữa các thùng với nhau để số thùng phải chở đi là ít nhất.
Yêu cầu: Cho dung lượng nước hiện có của thùng thứ $i$ là $B_i$ $(0 \le B_i \le C_i,\ 1 \le i \le N)$, hãy giúp ông Nam xác định số lượng thùng ít nhất phải mang đi.
Input:
- Dòng thứ nhất ghi một số tự nhiên $N$ là số lượng các thùng nước.
- Dòng thứ $i$ trong $N$ dòng tiếp theo mỗi dòng có 2 số nguyên $B_i$ và $C_i$ $(0 \le B_i \le C_i)$ mô tả thông tin thùng thứ $i$, với $B_i$ là nước còn trong thùng và $C_i$ là sức chứa của thùng, các số cách nhau ít nhất một khoảng trắng.
Output:
- Số duy nhất là số lượng ít nhất các thùng nước phải chở đi.
4
0 1
4 5
0 2
1 21Giải thích: Sau khi san nước giữa các thùng thì ông Nam chỉ cần chở đi thùng số 2 để đổ nước mang về.
Đổ hết nước vào 3 thùng nhỏ nhất (sức chứa 1, 2, 2) là vừa khít 5 đơn vị, chỉ còn thùng số 2 (sức chứa 5) là chưa đầy.
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 CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngTư tưởng tham lam (Greedy)
Bài này dùng tư tưởng tham lam để giải quyết. Kể cả bạn nào có không biết về tư tưởng tham lam này thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết đó. Cho bạn nào không biết thì mình có thể nói nhanh như thế này:
Thì tại sao bài này lại có thể nhìn ra tư tưởng của nó là tham lam? Đọc kỹ đề ta sẽ thấy yêu cầu là hãy cố gắng san lượng nước hiện tại đang có vào các thùng, những thùng nào chưa đầy thì sẽ được chở đi, và làm sao để số lượng thùng phải chở đi là ít nhất.
Ta sẽ hiểu rằng để số thùng chở đi là ít nhất thì phải cố gắng lấp đầy lượng nước hiện tại vào được nhiều thùng nhất có thể, thì số lượng thùng chưa đầy cần chở đi lúc này sẽ là ít nhất. Chính từ chỗ cố gắng lấp đầy được càng nhiều thùng càng tốt thì đây chính là tư tưởng của tham lam dễ dàng để nhìn ra. Thực ra đây cũng là tư tưởng từ thực tế thôi, nếu xét theo thực tế thì cũng phải làm như vậy.
Triển khaiĐổ vào thùng nhỏ nhất trước
Muốn lấp đầy được nhiều thùng nhất thì dĩ nhiên ta phải ưu tiên lấp những thùng có sức chứa nhỏ trước (tốn ít nước nhất). Cách thức triển khai như sau:
- Có một biến tổng
sum: trong quá trình đọc dữ liệu đầu vào, lượng nước hiện có $B_i$ của mỗi thùng ta cộng dồn vào biến tổng, còn sức chứa $C_i$ của từng thùng thì đưa vào mảng 1 chiềuađể lưu trữ. - Sắp xếp mảng sức chứa
atăng dần. - Xét từ đầu mảng (thùng có sức chứa bé nhất trở lên, $i = 0, 1, 2\dots$): nếu
sum >= a[i]thì thùng $i$ được lấp đầy, biến tổng bị trừ đia[i]rồi xét tiếp thùng sau. - Đến thời điểm nào mà
sum < a[i]thì thùng thứ $i$ không lấp đầy được, vậy từ thùng thứ $i$ đến cuối chính là các thùng phải chở đi, số lượng là $N - i$. In ra kết quả và kết thúc chương trình luôn. - Cần lưu ý tình huống vòng lặp chạy đến tận cùng mà vẫn không xuất ra kết quả (khi toàn bộ các thùng đều được lấp đầy), thì sau cùng nhớ xuất ra 0 (không có thùng nào phải chở đi).
| i | a[i] (đã sắp) | sum ≥ a[i]? | Xử lý |
|---|---|---|---|
| 0 | 1 | 5 ≥ 1 | Lấp đầy, sum = 5 − 1 = 4 |
| 1 | 2 | 4 ≥ 2 | Lấp đầy, sum = 4 − 2 = 2 |
| 2 | 2 | 2 ≥ 2 | Lấp đầy, sum = 2 − 2 = 0 |
| 3 | 5 | 0 < 5 | Dừng! In N − i = 4 − 3 = 1 |
Chạy với ví dụ đề: tổng nước $0 + 4 + 0 + 1 = 5$, sức chứa sau khi sắp tăng dần là $1, 2, 2, 5$.
sum. Mà tổng sức chứa của $k$ thùng nhỏ nhất luôn $\le$ tổng sức chứa của $k$ thùng bất kỳ, nên $k$ thùng nhỏ nhất cũng lấp đầy được. Vậy chỉ cần lấp lần lượt các thùng nhỏ nhất là đạt được số thùng đầy nhiều nhất. (Phần nước dư còn lại thì đổ vào thùng tiếp theo, đằng nào thùng đó cũng phải chở đi.)Em nhập lượng nước $B$ và sức chứa $C$ của các thùng rồi bấm Tiếp để xem từng bước san nước:
100%Code O(N log N)
sort trong thư viện algorithm, nó đã được code tối ưu luôn đảm bảo $O(N \log N)$ và gọi ra nhanh gọn để xài.long long (64 bit), bởi có tối đa $10^6$ thùng, mỗi thùng tối đa $10^7$. Trường hợp lớn nhất biến tổng phải lưu đến $10^7 \cdot 10^6 = 10^{13}$ (10 nghìn tỷ), mà kiểu 32 bit chỉ lưu được cỡ $2 \cdot 10^9$ (thực ra hơn 2 tỷ xíu) thì không nổi, phải dùng kiểu 64 bit mới lưu nổi nhé.scanf của C để đọc sẽ tốt hơn cin của C++. Hoặc bạn nào quen dùng cin thì tham khảo 2 dòng đầu tiên trong hàm main của mình dưới đây.Source code cho anh em tham khảo với tư tưởng xử lý mình trình bày ở trên:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int a[maxn + 5];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
long long sum = 0;
for(int i = 0; i < n; ++i){
int b;
cin >> b >> a[i];
sum += b;
}
sort(a, a + n);
for(int i = 0; i < n; ++i){
if(sum >= a[i]){
sum -= a[i];
}
else{
cout << n - i;
return 0;
}
}
cout << 0;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
total = sum(map(int, data[1:2 * n + 1:2])) # tổng lượng nước B[i]
a = sorted(map(int, data[2:2 * n + 2:2])) # sức chứa C[i] tăng dần
ans = 0
for i in range(n):
if total >= a[i]:
total -= a[i]
else:
ans = n - i
break
print(ans)Giả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 cần nhập xuất nhiều, như bài này có tới $2 \cdot 10^6$ số cần đọc vào, ta hãy nên để 2 dòng này vào để 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é.- Mảng
akhai báo toàn cục với kích thướcmaxn + 5$= 10^6 + 5$: mảng lớn như vậy nếu khai báo trong hàmmaincó thể tràn bộ nhớ stack, để ra ngoài làm biến toàn cục thì an toàn. - Lượng nước
bcủa mỗi thùng không cần lưu lại, chỉ cộng dồn vàosumlà đủ, vì sau khi san nước thì nước ở thùng nào cũng như nhau. - Khi gặp thùng đầu tiên không lấp đầy được, in
n - irồireturn 0kết thúc luôn; nếu vòng lặp chạy hết thì in0.
Thời gian gồm $O(N)$ của bước đọc dữ liệu + $O(N \log N)$ của bước sắp xếp mảng tăng dần + $O(N)$ của bước duyệt mảng trừ dần biến tổng. Theo quy tắc cộng của BigO ta lấy thành phần lớn nhất, nên độ phức tạp tổng quát là $O(N \log N)$.
Với $N$ lớn nhất là $10^6$ thì yên tâm sẽ AC được, vì với giới hạn 1 giây thì số lần lặp tối đa được phép ở ngưỡng $(3 \text{ đến } 5) \cdot 10^7$. Tính chi tiết cả thảy sẽ là $10^6 + 10^6 \cdot \log_2(10^6) + 10^6$ $\approx 22 \cdot 10^6$ $\approx 3 \cdot 10^7$, vẫn ở ngưỡng tối đa được phép. Không gian là $O(N)$ do cần mảng lưu sức chứa của $N$ thùng.
long long.
Nhận xét
Đăng nhận xét