Giả sử chúng ta có một chuỗi S với n ký tự. S chứa các chữ cái tiếng Anh viết thường và ký tự ')'. Chuỗi được coi là xấu, nếu số ký tự ')' ở cuối chuỗi lớn hơn chặt số các ký tự còn lại. Chúng ta phải kiểm tra xem S có xấu hay không.
Ví dụ, nếu đầu vào là S = "fega))))))", thì đầu ra sẽ là True, vì chuỗi này xấu do có 4 chữ cái và 6 ký tự ')'.
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:
ans := 0 n := kích thước của S i := n - 1 while (i >= 0 và S[i] giống ')'), do: (giảm i đi 1) z := n - 1 - i ans := 2 * z - n if ans > 0, thì: return true Ngược lại return false
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; bool solve(string S) { int ans = 0; int n = S.size(); int i = n - 1; while (i >= 0 && S[i] == ')') i--; int z = n - 1 - i; ans = 2 * z - n; if (ans > 0) return true; else return false; } int main() { string S = "fega))))))"; cout << solve(S) << endl; }Đầu vào
"fega))))))"
Đầu ra
1