f634 - 士兵歸來
題目描述
題目要求統計一場戰役中各軍種（海軍、陸軍、空軍）和各軍階（軍官、士官、士兵）的存活人數，以及計算存活率。輸入包含士兵的姓名、軍種和軍階，需要處理同名同姓的情況，只計算姓名、軍種和軍階都相同的人一次。
解題思路
使用一個 map 來儲存士兵的資訊，map 的鍵是士兵的姓名，值是一個結構體 tp，該結構體包含一個 4x4 的布林陣列 a。這個陣列用於記錄特定姓名、軍種和軍階的士兵是否已經被計算過。
程式首先讀取士兵的數量 N 和報到記錄的數量 M。然後，迴圈讀取每一條報到記錄，提取姓名、軍種和軍階。如果該士兵尚未被計算過（即 name[t].a[x][y] 為 0），則將其標記為已計算，並更新對應軍種和軍階的計數器。
最後，程式輸出各軍種的存活人數、各軍階的存活人數以及存活率。
複雜度分析
- 時間複雜度: O(M)，其中 M 是報到記錄的數量。
map的查找、插入和更新操作平均時間複雜度為 O(log M)，但由於題目中 M 的最大值為 1,000,000，因此可以近似認為是 O(1)。迴圈遍歷 M 次，因此總時間複雜度為 O(M)。 - 空間複雜度: O(M)，因為
map最多會儲存 M 個不同的士兵資訊。結構體tp的大小是固定的，因此不影響空間複雜度的主要因素。
程式碼
#include <iostream>
#include <iomanip>
#include <map>
using namespace std;
struct tp{
bool a[4][4];
};
int ans[4][4];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,m,x,y,total=0;
string t;
map <string,tp> name;
cin >> n >> m;
while(m--){
cin >> t >> x >> y;
if(name[t].a[x][y]==0){
name[t].a[x][y]=1;
ans[x][y]++;
++total;
}
}
for(int i=1;i<4;++i){
if(i==1)
cout << "navy:";
else if(i==2)
cout << "army:";
else
cout << "air:";
cout << ans[i][3]+ans[i][1]+ans[i][2] << " ";
}
cout << "\n";
for(int i=1;i<4;++i){
if(i==1)
cout << "officer:";
else if(i==2)
cout << "sergeant:";
else
cout << "soldier:";
cout << ans[3][i]+ans[1][i]+ans[2][i] << " ";
}
cout << "\nsurvival rate: ";
float t1=n,t2=total;
cout << fixed << setprecision(1) << t2/t1*100 << "%\n";
}