d492 - 10226 - Hardwood species
題目描述
題目要求讀取多組樹木名稱的輸入，並計算每種樹木在每組輸入中出現的百分比。輸出結果需要按照樹木名稱的字典順序排列，並保留小數點後四位。
解題思路
這題的核心是統計每種樹木出現的次數，然後計算其百分比。可以使用 map 資料結構來儲存樹木名稱和其出現次數。map 能夠自動按照鍵（樹木名稱）進行排序。程式首先讀取測試案例的數量，然後對於每個測試案例，讀取樹木名稱直到遇到空行。在讀取過程中，使用 map 統計每種樹木的出現次數。讀取完所有樹木後，計算每種樹木的百分比，並按照字典順序輸出結果。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是所有樹木名稱的總數。
map的插入和查找操作平均時間複雜度為 O(log N)，需要遍歷所有樹木名稱。 - 空間複雜度: O(K)，其中 K 是不同樹木名稱的數量。
map儲存了所有不同的樹木名稱和其出現次數。
程式碼
#include <iostream>
#include <map>
#include <string>
#include <iomanip>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int t;
float n;
string a;
cin >> t;
getline(cin,a);
getline(cin,a);
while(t--){
map <string,float> ans;
n=0;
while(getline(cin, a) && a != "" ){
ans[a]++;
n++;
}
for(auto i=ans.begin();i!=ans.end();i++)
cout << i->first << " " << fixed << setprecision(4) << i->second/n*100 << "\n";
if(t!=0)
cout << "\n";
}
}