Giả sử chúng ta có một chuỗi S với 'L', 'R' và các chữ số từ 0 đến 9. Xét một khách sạn có 10 phòng được đánh số từ 0 đến 9, từ trái sang phải. Khách sạn có hai lối vào — một từ bên trái, và một từ bên phải. Khi khách đến qua lối vào trái, họ nhận phòng trống gần lối vào trái nhất. Tương tự, khi khách đến qua lối vào phải, họ nhận phòng trống gần lối vào phải nhất. Nhưng chúng ta đã mất danh sách phân phòng. Nhưng chúng ta nhớ tất cả khách: khi khách đến, từ lối nào, và khi họ rời khách sạn. Ban đầu khách sạn trống. Chúng ta phải khôi phục danh sách phân phòng từ ký ức. Trong S, 'L' nghĩa là người đến từ bên trái, nếu là 'R' họ đến từ bên phải, và chữ số d chỉ ra khách rời phòng d. Chúng ta phải trả về trạng thái phòng. Một chuỗi độ dài 10 mà nếu là 0 nghĩa là phòng trống, ngược lại là đang được chiếm.
Ví dụ, nếu đầu vào là S = "LLRL1RL1", thì đầu ra sẽ là "1010000011", vì
Đầu tiên, tất cả phòng trống. Trạng thái 0000000000.
L - Khách đến qua lối trái. Trạng thái 1000000000.
L - Khách từ lối trái. Trạng thái 1100000000.
R - Khách từ lối phải. Trạng thái 1100000001.
L - Khách từ lối trái. Trạng thái 1110000001.
1 - Khách ở phòng 1 rời. Trạng thái 1010000001.
R - Khách từ lối phải. Trạng thái 1010000011.
L - Khách từ lối trái. Trạng thái 1110000011.
1 - Khách ở phòng 1 rời. Trạng thái 1010000011.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
n := kích thước của S a := "0000000000" for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: if S[i] giống 'L', thì: đặt 0 ngoài cùng bên trái trong a thành 1 if S[i] giống 'R', thì: đặt 0 ngoài cùng bên phải trong a thành 1 Ngược lại đặt vị trí S[i] trong a thành 0 return a
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; string solve(string S) { int n = S.size(); string a = "0000000000"; for (int i = 0; i < n; i++) { if (S[i] == 'L') a[a.find('0')] = '1'; if (S[i] == 'R') a[a.rfind('0')] = '1'; else a[S[i] - '0'] = '0'; } return a; } int main() { string S = "LLRL1RL1"; cout << solve(S) << endl; }Đầu vào
"LLRL1RL1"
Đầu ra
1010000011