e780 - Error

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個禮物交換的過程。一開始有一個整數 x 代表目前的位置。輸入包含一系列指令，可以是 "L" (向左移動)，"R" (向右移動)，或 "Gift" (收到禮物)。如果收到禮物，且禮物的位置等於目前的位置 x，則答案加一。最終輸出答案。

解題思路

這題主要使用模擬的方式來解決。我們維護一個變數 x 代表目前的位置，並根據輸入的指令更新 x 的值。當輸入為 "Gift" 時，讀取禮物的位置 gift，如果 x 等於 gift，則將答案 ans 加一。最後輸出 ans。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入的指令數量。因為我們需要遍歷所有指令一次。
• 空間複雜度: O(1)，因為我們只使用了幾個常數大小的變數。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	int n,x=0,gift,ans=0;
	string a;
	cin >> n;
	while(n--){
		cin >> a;
		if(a=="Gift"){
			cin >> gift;
			if(x==gift)
				ans++;
		}
		else if(a=="L")
			x--;
		else
			x++;
	}
	cout << ans ;
}