e302 - PI. Inherit Previous Exam(繼承考古題)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了大學生之間考古題傳遞的情況。有些學生產生考古題（Y），有些學生消耗考古題（N）。要求判斷是否能完美使用所有考古題，且沒有學生因沒有考古題而「被當掉」（消耗多於擁有的考古題），也沒有學生產生的考古題沒有被使用。

解題思路

這題的核心是模擬考古題的傳遞過程。使用一個計數器 ans 來追蹤目前擁有的考古題數量。遇到 'Y' 時，ans 增加 1；遇到 'N' 時，ans 減少 1。如果 ans 變為負數，表示有學生消耗了不存在的考古題，直接判斷為 "NO"。在遍歷完所有學生資料後，如果 ans 大於 0，表示還有未使用的考古題，也判斷為 "NO"。只有當 ans 等於 0 時，才表示所有考古題都被完美使用，輸出 "YES"。

複雜度分析

• 時間複雜度: O(n)，其中 n 是字串 S 的長度。因為程式碼需要遍歷字串 S 一次。
• 空間複雜度: O(1)，程式碼只使用了常數個變數，不隨輸入大小而變化。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	string a;
	cin >> a;
	while(cin >> a){
		int ans=0;
		bool c=1;
		for(int i=0;i<a.length();i++){
			if(a[i]=='Y')
				ans++;	
			else if(a[i]=='N')
				ans--;
			if(ans<0){
				c=0;
				break;
			}
		}
		if(ans>0)
			c=0;
		if(c==1)
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}