b265 - Q11286 - Conformity
題目描述
題目要求計算在給定的學生課程選擇中，最受歡迎的課程組合有多少學生選擇。每位學生選擇 5 門課程，課程代碼在 100 到 499 之間。輸入包含多組測試資料，每組資料以學生人數 n 開始，然後是 n 行，每行包含 5 個課程代碼。當 n 為 0 時，表示輸入結束。
解題思路
解題思路是使用雜湊表 (map) 統計每個課程組合出現的次數。對於每組輸入，首先讀取學生人數 n。然後，對於每個學生，讀取其選擇的 5 門課程，將課程排序，並將排序後的課程組合作為雜湊表的鍵，值為該組合出現的次數。在統計完所有學生的課程選擇後，找到雜湊表中出現次數最多的課程組合，並輸出該組合出現的次數。
複雜度分析
- 時間複雜度: O(n * k * log k)，其中 n 是學生人數，k 是每位學生選擇的課程數量 (本題中 k=5)。排序每位學生的課程需要 O(k log k) 的時間，遍歷所有學生需要 O(n) 的時間。雜湊表的插入和查找操作平均時間複雜度為 O(1)。
- 空間複雜度: O(n)，最壞情況下，所有學生的課程組合都不同，雜湊表需要存儲 n 個不同的課程組合。
程式碼
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
string a[5];
while(cin >> n){
if(n==0)break;
map <string, int> arr;
map <string, int>::iterator it;
int ans=1,p=0;
while(n--){
for(int i=0;i<5;++i)
cin >> a[i];
sort(a,a+5);
string t;
for(int i=0;i<5;++i)
t+=a[i];
++arr[t];
ans=max(ans,arr[t]);
}
for(it=arr.begin();it!=arr.end();++it)
if(it->second==ans)
p+=it->second;
cout << p << "\n";
}
}