Hướng dẫn giải của [200 đề thầy Đức] Bài 30: Xếp hàng uống nước
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Học sinh đến hàng vào giây L[i]; mỗi giây người đầu hàng lấy nước đúng 1 giây. Ai đến giây R[i] mà vẫn chưa được lấy nước thì rời hàng (kết quả 0). Vì L không giảm theo số hiệu nên hàng đợi luôn xếp đúng theo số hiệu. Ta mô phỏng từng giây.
Sub 1: Vét cạn — ~O(T_{max} \cdot N)~
Mô phỏng từng giây t = 1..5000. Mỗi giây, đánh dấu những học sinh đã quá giờ (R < t), sau đó tìm học sinh có số hiệu nhỏ nhất đã đến và chưa xong rồi cho lấy nước trong giây t. Cách này đúng hoàn toàn, đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> L(n), R(n), ans(n, 0);
vector<bool> xong(n, false); // da lay nuoc hoac da roi hang
for (int i = 0; i < n; i++) cin >> L[i] >> R[i];
// Mo phong tung giay t
for (int t = 1; t <= 5000; t++) {
// Ai qua giay R ma chua lay duoc nuoc thi roi hang (ans = 0)
for (int i = 0; i < n; i++)
if (!xong[i] && R[i] < t) xong[i] = true;
// Nguoi dau hang la nguoi co so hieu nho nhat da den va chua xong
for (int i = 0; i < n; i++) {
if (!xong[i] && L[i] <= t) {
ans[i] = t; // lay nuoc trong giay t
xong[i] = true;
break;
}
}
}
for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? ' ' : '\n');
}
return 0;
}
Sub 2: Hàng đợi (deque) — ~O(T_{max} + N)~
Dùng deque làm hàng đợi thật. Mỗi giây: đưa những học sinh vừa đến vào cuối hàng, bỏ những người ở đầu hàng đã quá giờ (R < t), rồi người đầu hàng lấy nước.
Bẫy cần chú ý: người có R = t vẫn còn được lấy nước trong giây t, nên điều kiện bỏ là R < t (không phải R ≤ t). Người đã quá giờ nằm giữa hàng không cần xóa ngay; khi họ lên đầu hàng thì sẽ bị bỏ qua và kết quả vẫn là 0. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> L(n), R(n), ans(n, 0);
for (int i = 0; i < n; i++) cin >> L[i] >> R[i];
// L khong giam nen hang doi luon xep theo so hieu: dung hang doi FIFO
deque<int> hang;
int nxt = 0;
for (int t = 1; t <= 5000; t++) {
// Hoc sinh den vao cuoi hang trong giay t
while (nxt < n && L[nxt] <= t) hang.push_back(nxt++);
// Bo qua nhung ban da roi hang (den giay truoc R ma chua uong): ans giu 0
// Den giay R van con duoc lay nuoc, nen chi bo khi R < t
while (!hang.empty() && R[hang.front()] < t) hang.pop_front();
// Nguoi dau hang lay nuoc dung 1 giay
if (!hang.empty()) {
ans[hang.front()] = t;
hang.pop_front();
}
}
for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? ' ' : '\n');
}
return 0;
}
Bình luận