「眾裡尋他（她）千百度，驀然回首，那人卻在燈火闌珊處。」如果讓你當月下老人，你能夠把看對眼的兩個有緣人盡量湊成一對，不要讓遺憾發生嗎？我們將給你一份等待配對的名單，其中「p」代表男生，「q」代表女生，配對的條件很簡單，只要 p 跟 q 的位置是「面對面」（亦即「pq」），就代表彼此相看兩不厭，可被視為一對，其他的狀態，如背對背 (亦即「qp」、「pp」或「qq」），則不能配對成功。成功配對後，該 pq 對就被移出等候配對名單，讓其他的 p 與 q 可以有機會繼續配對。你的目標就是盡量找出所有可以配成對的 p 與 q。能否圓滿達成任務，就靠你智慧的安排！願天下有情人終成眷屬！
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行是一個整數 N，代表有 N 組 (行) 的等候配對名單。 每一組名單中，p 與 q 之間可能相鄰或者以「.」分隔，「.」的數量多寡不定，但不影響 p 與 q 的配對 (距離不是問題！），亦即除了 pq 以外，p.q、p….q 等都可以配成對。 | 輸出能成功配成對的最大總數，輸出的每一行對應一組等候名單。 |
| 2 ..p..p.p…q.q. .p…qq..p.pq.p..q.qpp..qpq | 2 6 |
解題思路
將一整行以字串的方式收起來，並且宣告一個 Vector<char>，對字串中的每一個字元進行判斷。
如果目前字元是「q」的話，則要先判斷 Vector 中有沒有資料，如果有的話，判斷最後一個資料是否為「p」，如果是的話將答案 +1 並且將 Vector 進行 pop_back()。如果上面的不成立則將目前字元 Push_Back 到 Vector 中。「.」這個字元一律不做判斷也不用存到 Vector 中。
範例程式碼－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