e839 - P6. 飲食分類 (Food)
題目描述
題目要求根據輸入的食物及其種類，查詢特定種類的食物，並按照字典順序輸出這些食物的名稱。如果沒有該種類的食物，則輸出 "No"。
解題思路
使用一個 map (Hash Table) 來儲存食物種類和對應食物名稱的關聯。map 的 key 是食物種類 (string)，value 是包含該種類所有食物名稱的字串，食物名稱之間用空格分隔。
讀取輸入的食物和種類資訊，將其儲存在 map 中。
讀取要查詢的食物種類 c。
如果 map 中不存在該種類，則輸出 "No"。
如果存在，則從 map 中獲取該種類的所有食物名稱，使用空格分割成一個字串陣列，對陣列進行排序，然後逐個輸出排序後的食物名稱。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是食物的數量。主要時間花在排序食物名稱的字串陣列上。
map的插入和查找操作平均時間複雜度為 O(log N)，但由於題目限制 N <= 50，可以近似認為是 O(1)。 - 空間複雜度: O(N)，主要用於儲存
map和字串陣列。
程式碼
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
string a,b,c;
string an[50];
map <string,string> ans;
while(n--){
cin >> a >> b;
ans[b]+=a;
ans[b]+=' ';
}
cin >> c;
if(ans.find(c)==ans.end()){
cout << "No\n";
}
else{
int j=0,t=0;
string i=ans[c],d;
for(int il=i.length();j<il;j++){
if(i[j]!=' '){
d+=i[j];
}
else{
an[t]=d;
d.clear();
t++;
}
}
sort(an,an+t);
for(int i=0;i<t;i++){
cout << an[i] << "\n";
}
}
}