"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. 每一組名單中，p 與 q 之間可能相鄰或者以「.」分隔，「.」的數量多寡不定，但不影響 p 與 q 的配對 (距離不是問題！），亦即除了 pq 以外，p.q、p….q 等都可以配成對。 | 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
將一整行以字串的方式收起來，並且宣告一個 Vector<char>，對字串中的每一個字元進行判斷。
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