UVa 555

題目

http://domen111.github.io/UVa-Easy-Viewer/?555

現在我們要來玩一場橋牌，一場橋牌當中會有一個玩家負責發牌，並且我們會以方位(N, E, S, W)來稱呼玩家

發牌會從發牌者的左手邊開始，逆時針方向發牌，直到第 52 張牌被發到發牌玩家

在發牌結束後，我們需要將所有玩家的手牌依照其大小由小到大排序

每張牌都會有一個花色以及一個數字，其大小順序如下

• 花色
  C < D < S < H
• 數字
  2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A

最後依照 S W N E 的順序輸出排序後的手牌

想法

就直接照著題目的意思去模擬

排序的部分自訂一個 compare function

如果要避免寫太多 if-else 來判斷彼此之間的大小，可以預先建立一個表儲存每個元素對應到的數字

只要保證這些數字之間的大小關係跟題目中要求的元素之間大小關係相同即可

Code

// By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int player, pos[128], order[128];
char n, color, number;
string card, cards[4][13];
// 為了方便建表，這裡先建立兩個已經排好的字串
string pos_str="SWNE", card_str="CDSH23456789TJQKA";

bool cmp(string p, string q){
	// 直接比較元素之間的大小關係即可
	if(order[p[0]] != order[q[0]]) return order[p[0]] < order[q[0]];
	else if(order[p[1]] != order[q[1]]) return order[p[1]] < order[q[1]];
	else return false;
}

int main(){
	// 預先建方位對應數字的表
	for(int i=0 ; i<4 ; i++){
		pos[pos_str[i]] = i;
	}
	// 預先建立卡牌顏色以及數字對應的數字表
	for(int i=0 ; i<card_str.size() ; i++){
		order[card_str[i]] = i;
	}
	
	while(cin>>n && n!='#'){
		// 這裡可以直接用數字表示方位了!
		player = pos[n];
		for(int i=0, j=0 ; i<52 ; i++){
			// 每次都是發給下一位玩家
			player = (player+1)%4;
			cin>>color>>number;
			// 把顏色以及數字串起來
			// 注意不能直接用字原相加
			card = "";
			card.push_back(color);
			card.push_back(number);
			cards[player][j] = card;
			// 每經過 4 次，就表示已經發完一輪牌了
			if((i+1)%4 == 0) j++;
		}
		
		for(int i=0 ; i<4 ; i++){
			sort(&cards[i][0], &cards[i][13], cmp);
		}
		
		for(int i=0 ; i<4 ; i++){
			cout<<pos_str[i]<<": ";
			for(int j=0 ; j<13 ; j++){
				if(j!=0) cout<<" ";
				cout<<cards[i][j];
			}
			cout<<"\n";
		}
	}
	return 0;
}

時間複雜度分析

預處理時間複雜度為 $O(1)$ ($O(21)$可以直接視為常數)

每筆測資輸入時間複雜度為 $O(n)$ ($n = 52$)

每筆測資排序時間複雜度為 $O(nlogn)$

每筆測資輸出時間複雜度為 $O(n)$

每筆測資總時間複雜度為 $O(n + nlogn)$