Giả sử chúng ta có một chuỗi S độ dài n, chỉ có hai loại ký tự, 'A' hoặc 'P'. Có n sinh viên xếp hàng, sinh viên thứ i đang giận nếu S[i] = 'A', nếu là 'P' nghĩa là S[i] kiên nhẫn. Một sinh viên giận tại chỉ số i sẽ đánh sinh viên kiên nhẫn tại chỉ số i+1 mỗi phút, và đối với sinh viên cuối cùng dù anh ta có giận, anh ta cũng không thể đánh ai. Sau khi đánh một sinh viên kiên nhẫn, sinh viên đó cũng trở nên giận. Chúng ta phải tìm số phút tối thiểu sau đó không có sinh viên mới bị giận.
Ví dụ, nếu đầu vào là S = "PPAPP", thì đầu ra sẽ là 2, vì sau phút đầu tiên, chuỗi sẽ là "PPAAP", rồi phút thứ hai "PPAAA", sau đó không có sinh viên mới bị giận nữa.
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 ans := 0, cnt = 0 for khởi tạo i := n - 1, khi i >= 0, cập nhật (giảm i đi 1), do: if S[i] giống 'P', thì: (tăng cnt lên 1) Ngược lại ans := maximum của ans và cnt cnt := 0 return ans
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(string S) { int n = S.size(); int ans = 0, cnt = 0; for (int i = n - 1; i >= 0; i--) { if (S[i] == 'P') { cnt++; } else { ans = max(ans, cnt); cnt = 0; } } return ans; } int main() { string S = "PPAPP"; cout << solve(S) << endl; }Đầu vào
PPAPP
Đầu ra
2