k202 - 13055 - Inception

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Dom Cobb 在多層夢境中穿梭的情境。需要模擬 Dom 的夢境進入和退出，並在 "Test" 查詢時輸出 Dom 目前所在的夢境擁有者，如果 Dom 不在任何夢境中，則輸出 "Not in a dream"。

解題思路

這題的核心是模擬夢境的進入和退出。可以使用一個字串陣列（或更精確地說是一個堆疊）來儲存夢境層級。 "Sleep" 命令將新的夢境擁有者推入堆疊，"Kick" 命令將當前夢境擁有者從堆疊中彈出，"Test" 命令則輸出堆疊頂端的夢境擁有者。如果堆疊為空，則表示 Dom 不在任何夢境中。

複雜度分析

• 時間複雜度: O(n)，其中 n 是查詢次數。因為每個查詢的操作（push, pop, top）都是常數時間。
• 空間複雜度: O(n)，在最壞的情況下，Dom 可能進入 n 層夢境，因此堆疊的大小可能達到 n。

程式碼

#include <iostream>
using namespace std;
int n,sz;
string a[10005],x;
int main(){
	cin.tie(0);cout.tie(0); ios::sync_with_stdio(0);
	cin >> n;
	while(n--){
		cin >> x;
		if(x=="Sleep"){
			cin >> a[sz++];
		}
		else if(x=="Test"){
			if(sz==0)cout << "Not in a dream\n";
			else cout << a[sz-1] << "\n";
		}
		else{
			if(sz)--sz;
		}
	}
}