k373 - 0 and 1 加強版??@@@!!!

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取題目名稱和完成狀態（0 或 1）。如果完成狀態為 0，則輸出題目名稱，但如果題目名稱已經輸出過，則不重複輸出。輸出順序應與輸入順序相同。

解題思路

這題的核心是記錄已經輸出過的題目名稱，以避免重複輸出。可以使用一個集合 (set) 來儲存已經輸出過的題目名稱。對於每一組輸入，如果完成狀態為 0，則檢查題目名稱是否已經在集合中。如果不在集合中，則輸出題目名稱，並將其加入集合。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入的題目數量。因為 set 的插入和查找操作平均時間複雜度為 O(1)。
• 空間複雜度: O(n)，因為 set 最多可能儲存 n 個不同的題目名稱。

程式碼

#include <iostream>
#include <set>
using namespace std;
set <string> st;
string s;
bool ac;
int main(){
	while(cin >> s >> ac){
		if(ac==0){
			if(st.count(s)==0){
				st.insert(s);
				cout << s << "\n";
			}
		}
	}
}