a743 - 10420 - List of Conquests

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一系列的國家和女性的名字，並統計每個國家有多少女性出現在列表中。最後，按照國家名稱的字母順序輸出每個國家及其對應的女性數量。

解題思路

這題的核心是統計每個國家出現的次數。可以使用 map 資料結構來儲存國家名稱和其對應的計數。程式首先讀取國家數量，然後逐行讀取輸入，提取每行中的國家名稱，並更新 map 中的計數。最後，按照 map 的鍵（國家名稱）的字母順序遍歷 map，輸出每個國家及其計數。

複雜度分析

• 時間複雜度: O(nm + klog(k))，其中 n 是輸入行數，m 是每行字串的平均長度，k 是不同國家的數量。O(nm) 是讀取和處理輸入的複雜度，O(klog(k)) 是 map 排序的複雜度。
• 空間複雜度: O(k)，其中 k 是不同國家的數量。這是因為 map 需要儲存每個國家的名稱和計數。

程式碼

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(){
	int a;
	string c;
	cin >> a;
	map <string,int> b;
	getline(cin,c);
	while(a--){
		string d;
		getline(cin,c);
		for(int i=0;i<c.length();i++){
			if(c[i]==' ')
				break;
			d+=c[i];
		}
		b[d]++;
	}
	for(auto i=b.begin();i!=b.end();i++)
		cout << i->first << " "<<i->second << "\n";
}