j604 - 10903 - Rock-Paper-Scissors Tournament
題目描述
題目描述了一場石頭剪刀布錦標賽，其中 n 名玩家互相進行 k 次遊戲。目標是計算每個玩家的平均獲勝次數，公式為 w/(w + l)，其中 w 是獲勝次數，l 是失敗次數。如果 w + l 為 0，則輸出 "-"。
解題思路
程式碼模擬了錦標賽的過程。它使用兩個陣列 ctw 和 ctl 來追蹤每個玩家的獲勝和失敗次數。對於每一場比賽，程式碼會比較兩個玩家的出拳，並根據石頭剪刀布的規則更新對應玩家的獲勝或失敗次數。最後，程式碼計算每個玩家的平均獲勝次數，並將結果輸出到小數點後三位。如果玩家沒有任何獲勝或失敗，則輸出 "-"。
複雜度分析
- 時間複雜度: O(k * n * (n - 1) + n)。主要的時間花在模擬 k * n * (n - 1) / 2 場比賽上，以及最後計算每個玩家的平均獲勝次數，這需要 O(n) 的時間。
- 空間複雜度: O(n)。程式碼使用兩個大小為 n + 1 的陣列
ctw和ctl來儲存每個玩家的獲勝和失敗次數。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,k;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
for(string sx,sy;cin >> n;cout << "\n"){
if(n==0)break;
cin >> k;
int ctw[101]={},ctl[101]={},x,y;
for(int i=0;i<k*n*(n-1)/2;++i){
cin >> x >> sx >> y >> sy;
if(sx=="rock")
(sy=="scissors")?++ctw[x],++ctl[y]:(sy=="paper")?++ctl[x],++ctw[y]:0;
else if(sx=="scissors")
(sy=="paper")?++ctw[x],++ctl[y]:(sy=="rock")?++ctl[x],++ctw[y]:0;
else
(sy=="rock")?++ctw[x],++ctl[y]:(sy=="scissors")?++ctl[x],++ctw[y]:0;
}
for(int i=1;i<=n;++i)
(ctl[i]+ctw[i]==0)?cout << "-\n":cout << fixed << setprecision(3) << (double)ctw[i]/(double)(ctl[i]+ctw[i]) << "\n";
}
}