Người Gửi: Dương Lee
- Problem:
Bob được ông chủ giao nhiệm vụ làm bảo vệ ở quán bar. Quán bar mới khai trương và mở cửa miễn phí, vì vậy rất đông khách tới. Do đó, mọi người phải xếp hàng lần lượt để vào trong quán bar, và nhiệm vụ của Bob là duy trì trật tự đường lối.
Để duy trì “cân bằng giới tính” trong quán bar, ông chủ mong muốn sự chênh lệch giữa nam và nữ không vượt quá X (X <= 100) trong suốt thời gian hoạt động. Bob cho mọi người xếp hàng và từng người vào một. Nếu như Bob để một người nào đó vào quán bar mà làm mất sự cân bằng giới tính, Bob sẽ bị ông chủ phạt. Vì vậy, Bob luôn đề phòng trước trường hợp này. Nếu như nó có thể xảy ra, Bob sẽ thông báo với mọi người rằng quán bar đã hết chỗ và đóng cửa quán lại, không cho ai vào nữa. N
ếu cứ cứng nhắc như thế này, Bob nhận thấy rằng có thể sẽ phải đóng cửa khá sớm và số lượng người vào trong quán bar khá ít. Vì vậy, anh đã linh hoạt hơn bằng cách cho người đứng thứ 2 trong hàng được phép vào trước, nếu như người đó không làm mất căn bằng giới tính trong quán bar.
Cho biết thứ tự mọi người xếp hàng, các bạn hãy tính xem với cách làm của Bob, số người được vào trong quán bar và uống rượu miễn phí là bao nhiêu?
Input
Dòng đầu tiên là số nguyên X.
Dòng thứ 2 là một xâu s, cho biết giới tính của những người đang xếp hàng. Kí tự ‘M’ thể hiện một người đàn ông, kí tự ‘W’ thể hiện một người phụ nữ trong hàng. Kí tự đầu tiên bên trái thể hiện cho người đứng ở vị trí đầu tiên của hàng.
Output
In ra số lượng người lớn nhất có thể vào trong quán bar.
Example:
Input
1
MWWMWMMWM
Output:
9
Input
2
WMMMMWWMMMWWMW
Output:
8
- Solution:
Input
2
WMMMMWWMMMWWMW
Output:
8
Giải thích test 2:
Tại vị trí người thứ 5, nếu để người này vào, sẽ làm mất cân bằng giới tính, vì vậy người đứng thứ 2 (W) sẽ được vào trước.
Hàng đợi lúc này còn lại MWMMMWWMW, trong quán bar hiện tại có 3 nam và 2 nữ.
Lượt thứ 6 và thứ 7, hai người tiếp vào bình thường, hàng đợi còn lại MMMWWMW, trong quán bar hiện tại có 4 nam và 3 nữ.
Lượt thứ 8, người tiếp (‘M’) vào bình thường, trong quán bar có 5 nam và 3 nữ. Sau lúc này không thể cho ai vào được nữa, Bob sẽ đóng cửa quán bar lại.
- Cách làm:
Mỗi lần duyệt người đầu tiên ([0]) tính toán trước nếu cho người đó vào thì có làm mất cân bằng không? Nếu không thì cho vào và update lại giới tính trong phòng + hàng đợi. Nếu có thì xét đến người tiếp theo ([1]) người tiếp theo mà cùng giới tính với người trước đó thì dừng trương trình vì không thể cho tiếp vào, còn nếu khác giớ thì lại tính toán trước xem có cho người đó vào được hay không? Nếu cho được thì cập nhật giới tính + hàng đợi. Nếu không thì thoát trương trình.
*Code dưới đây sử dụng thư viện vector để xử lí hàng đợi cho dễ. Nếu bạn làm bằng mảng thì cần cập nhật lại mảng và số lượng người trong mảng sau mỗi lần xóa người ra khỏi hàng đợi.