"Searching for him (her) among thousands, suddenly I turned, and there he (she) was, under the dim lights." If you were the matchmaker, could you pair up two people who fancy each other as much as possible and prevent any regrets? We will give you a list of people waiting to be matched. In this list, "p" represents a man, and "q" represents a woman. The matching condition is simple: as long as the positions of p and q are "face to face" (i.e., "pq"), it means they are mutually attracted and can be considered a pair. Other states, such as back-to-back (i.e., "qp", "pp", or "qq"), cannot form a successful match. After a successful match, the "pq" pair will be removed from the waiting list, allowing other p's and q's to have a chance to be matched. Your goal is to find as many matching pairs of p's and q's as possible. Can you fulfill this task perfectly with your wise arrangement? May all lovers in the world become a happy couple!
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line is an integer N, representing the number of groups (rows) in the waiting list for matching. In each group of the list, p and q may be adjacent or separated by ".", the number of which can vary, but it does not affect the matching of p and q (distance is not an issue!). That is, in addition to pq, p.q, p...q, etc., can also be matched as pairs. | Output the maximum total number of successful pairs. Each line of the output corresponds to a group on the waiting list. |
| 2 ..p..p.p…q.q. .p…qq..p.pq.p..q.qpp..qpq | 2 6 |
Thought Process
Store an entire line as a string, and then declare a Vector to evaluate each character in the string.
If the current character is "q", first check if the vector contains any data. If it does, examine if the last item is "p". If so, increment the answer by 1 and perform a pop_back() operation on the vector. If these conditions are not met, push the current character back into the vector. The character "." is not evaluated and should not be stored in the vector under any circumstance.
Sample Code－ZeroJudge A565: p&q
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++) {
string str;
cin >> str;
vector<char>v;
int ans = 0;
for (int j = 0; j<str.length(); j++) {
const char ch = str[j];
if (ch != '.') {
if (ch == 'q' && !v.empty()) {
if (v[v.size()-1] == 'p') {
ans++;
v.pop_back();
continue;
}
}
v.push_back(ch);
}
}
cout << ans << "\n";
}
}
//ZeroJudge A565
//Dr. SeanXD