【題解】Zerojudge a565 - 2.p&q的邂逅

題目連結

題目大意

給定一串由 $\text{pq.}$ 字元組成的字串，$\text{p}$ 若出現在 $\text{q}$ 左邊就可以配對，並移除。問最多可以湊成幾組配對？

題解

我們只需要紀錄 p 目前還剩下幾個，如果遇到 q 且 p 還有剩就把配對數量 $+1$，否則就直接忽略當前的 q。因為本題的輸入龐大，因此使用 getchar_unlocked() 函式讀取字元。需要特別注意的是在 scanf 裡面的 %d 後面要加上空白，吃掉第一行最後面的換行符號。剩下的實作細節請參考 code。關於 IO 優化的技巧可以參考我寫的【筆記】IO 優化這篇文章。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int tt;
	scanf("%d ", &tt);
	while(tt--) {
		int ans = 0;
		int cnt = 0;
		char c;
		while((c = getchar_unlocked()) != '\n') {
			if(c == 'p') {
				cnt++;
			} else if(c == 'q') {
				if(cnt > 0) {
					cnt--;
					ans++;
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge a565 - 2.p&q的邂逅