f769 - 可樂磷酸

🔗 前往 ZeroJudge 原題

題目描述

題目要求我們解析一個字串，字串由 'F'、'C' 和 'CA' 組成，分別代表臨末的朋友、不含磷酸的可樂和含磷酸的可樂。對於每個朋友 'F'，我們需要計算在其後面的可樂（'C' 和 'CA'）總數以及含磷酸可樂（'CA'）的數量。

解題思路

這題可以利用字串的特性，從後往前遍歷字串。當遇到 'F' 時，記錄當前 'x' (不含磷酸可樂數量) 和 'y' (含磷酸可樂數量) 的值，然後繼續往前遍歷，更新 'x' 和 'y' 的值。最後，按照 'F' 遇到的相反順序輸出每個朋友看到的總可樂數和含磷酸可樂數。由於題目限制字串長度，使用陣列儲存結果是可行的。

複雜度分析

• 時間複雜度: O(n)，其中 n 是字串的長度。因為我們需要遍歷字串一次。
• 空間複雜度: O(n)，其中 n 是字串的長度。因為我們使用了一個大小為 1500000 的陣列來儲存結果，最壞情況下可能需要儲存所有 'F' 及其對應的可樂數量。

程式碼

#include <iostream>
using namespace std;
int x,y,ans[1500000][2],it;
string s;
int main(){
	cin.tie(0);
	cout.tie(0); ios::sync_with_stdio(false);
	cin >> s;
	for(int i=s.length()-1;i>=0;--i){
		if(s[i]=='F'){
			ans[it][0]=x;
			ans[it][1]=y;
			++it;
		}
		else if(s[i]=='A'){
			++y;
		}
		else{
			++x;
		}
	}
	for(int i=it-1;i>=0;--i){
		cout << ans[i][0] << " " << ans[i][1] << "\n";
	} 
}