hello大家好呀，我是小樓，

上周參加了一個區的程式員技能比賽的初賽，其實就是演算法比賽，雖然最后結果是過了初賽，但程序真是一言難盡啊，

這次的演算法比賽和ACM非常類似，雖然我大學是數學專業，雖然大學也修過ACM這門課，但是我的演算法是真的不行，很菜很菜的那種，

好在這次比賽是組（抱大腿）隊模式，3人一組，3個小時時間，一共7道演算法題，1入門，2簡單，2中等，2困難，

10分鐘寫出入門題，但...

由于我知道我比較菜，所以比賽一開始，我就挑了一個看起來最簡單的題目做，難題交給隊友，

結果是3個小時過去，這個看起來最簡單的題目，愣是沒有做出來，下面就結合這道題講講我的心路歷程，

這道題的描述是這樣的：

看起來文字很多，其實要表達的很簡單，就是輸入一些成績，每個成績輸進去時，如果超過全班最好成績則輸出prefect，如果超過自己的最好成績則輸出great，如果沒超過自己最好成績則輸出bad，

是不是很簡單？用一個max變數保存全班最好成績，用一個map保存每個人的最好成績，不就解決了嗎？

不過這是我第一次用這個oj系統，連用戶都是剛注冊的，所以我還特地看了一會輸入輸出的demo，這次比賽只能使用ACM的輸入輸出模式，例如如果用的是Go語言，輸入輸出應該是這樣：

學會了輸入輸出之后，一口氣寫入如下的解法：

package main

import (
	"fmt"
)

func main() {
	var n int
	var name string
	var x float32
	var max float32
	scores := make(map[string]float32, n)

	fmt.Scan(&n)
	for i := 0; i < n; i++ {
		fmt.Scan(&name, &x)

		if x > max || i == 0 {
			fmt.Println("perfect")
			max = x
			scores[name] = x
		} else {
			if s, ok := scores[name]; ok {
				if x > s {
					fmt.Println("great")
					scores[name] = x
				} else {
					fmt.Println("bad")
				}
			} else {
				fmt.Println("great")
				scores[name] = x
			}
		}
	}
}

在我正得意，覺得這題10分鐘就能解決的時候，提交上去的代碼竟然超時了，在比賽時沒有截圖，提交后顯示有少數用例超過了2秒，oj的判定原理是準備一堆測驗用例，如果全部通過則判定為通過，當然這批測驗用例肯定不是那么好通過的，設計者會出各種極端的case，

優化map性能

調轉頭去仔細審題，果然時間和空間都有限制：

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 262144K，其他語言524288K

64bit IO Format: %lld

這題除了有map的讀寫，其他都是O(1)復雜度，性能不夠難道是map性能不夠？

如果是map的性能不夠，不夠在哪里呢？眾所周知，map的原理一般是這樣：

當一些key存入map時，會先對key計算hash值，在map中找到對應的hash槽，這個槽之后一般是個鏈表（有的語言也會做一些優化成樹狀，這里我們簡化為鏈表），因為不同的key的hash值可能會重復（沖突），沖突了只能把key排成一個鏈表，每次查找時都要遍歷鏈表，

所以有沒有可能，設計者給出了一堆hash值重復的name，數量又多，導致每次插入、查找時都要遍歷鏈表，性能下降，導致超時？

于是再仔細審題，我發現輸入的姓名和成績是有限制的：

name保證長度不超過6，僅由小寫英文字母組成，每個名字代表唯一一個同學

x為1位小數，0≤x≤300

name最長為6，且為小寫字母，這點給了我一點啟發，能不能讓查詢map變成O(1)復雜度？

顯然可以的，小寫字母范圍為a~z，如果看成數字就是1-26，也就是27進制，所以每個name可以表示為一個27進制的數，這樣就可以把所有人的成績放到一個大陣列里去，按name的27進制進行O(1)的查找，

為什么是27進制而不是26，因為name沒說是多少位，比如只有5位，那空出的一位怎么表示？只能用0表示了，a-z就是1-26，合起來是27進制，

參考10進制計演算法則，27進制應該這樣計算（以roshi為例）：

計算出的值即為陣列的下標，那么這個陣列的最大值是多少呢？

26 * 27^5 + 26 * 27^4 + 26 * 27^3 + 26 * 27^2 + 26 * 27^1 + 26 * 27^0

很容易算出來是：

387420488

需要這么大個陣列，大概3億多，輸入成績是個1位小數，可以轉換為int，大概4個位元組，掐指一算得 1513361KB，好像比要求的524288K多，先不管空間，寫一版跑跑看，萬一能過呢？

很簡單寫出代碼：

package main

import (
	"fmt"
)

func main() {
	var n int
	var name string
	var x int32

	fmt.Scan(&n)

	var scores [387420488]int32
	var exist [387420488]int32

	var max int32
	for i := 0; i < n; i++ {
		fmt.Scan(&name, &x)

		idx := mapIndex(name)

		if x > max || i == 0 {
			fmt.Printf("perfect\n")
			max = x
			scores[idx] = x
			exist[idx] = 1
		} else {
			if exist[idx] == 0 || x > scores[idx] {
				fmt.Printf("great\n")
				scores[idx] = x
				exist[idx] = 1
			} else {
				fmt.Printf("bad\n")
			}
		}
	}
}

var index27 = [6]int32{1, 27, 27 * 27, 27 * 27 * 27, 27 * 27 * 27 * 27}

func mapIndex(x string) int32 {
	var index int32
	for i := len(x) - 1; i >= 0; i-- {
		index = index + int32(x[i]-96)*index27[len(x)-1-i]
	}
	return index
}

結果竟然報錯了，我當時不理解，事后理解了，我們暫且不說，后面會說到原因，

就是因為這個報錯不明不白，明明能測驗通過，到底哪里理解有偏差？亦或是記憶體超了？

優化記憶體占用

上面的代碼用到了2個陣列，一個存最大值，一個存值是否存在，一個陣列是1513361KB，2個就是3026722KB，是最大記憶體限制的5.7倍

var scores [387420488]int32
var exist [387420488]int32

exist陣列可以用boolean型別，分數最大值0<=0<=300，int16足矣

	大小	范圍
int8	1位元組	-128 ~ 127
int16	2位元組	-32768 ~ 32767
int32	4位元組	-2147483648 ~ 2147483647

如果是這個組合，將占用 1135020KB，是上限的2倍多，還是有點超，先試試：

還是一樣，難道是我演算法有問題？沒道理啊，到這里我實在是沒招了，3小時也耗盡了，比賽結束，

賽后思考

賽后，我拿著這道題去找了一位剛入職位元組的朋友，想著剛去位元組應該刷過不少題吧，果然大佬就是大佬，給出了一個有新意的思路，用前綴樹做：

每一個name都構造出一個前綴樹，查找時最多只需要查找6次，記憶體使用應該也不會太多，算是時間與空間的一個平衡，

大佬還補充了一句：比賽還是比較特殊的，可能就是某一個case卡主了，而你要做的就是如何能把這個特殊的case也ac掉，

大佬的話似乎很有道理，于是我寫了一個前綴樹的版本：

package main

import (
	"fmt"
)

type treeNode struct {
	max  float32
	next [26]*treeNode
}

func main() {
	var n int
	var name string
	var x float32
	fmt.Scan(&n)

	var max float32
	tree := new(treeNode)
	for i := 0; i < n; i++ {
		fmt.Scan(&name, &x)

		if x > max || i == 0 {
			fmt.Println("perfect")
			max = x
			insert(tree, name, x)
		} else {
			if tmp := searchAndStoreMax(tree, name, x); tmp != -1 {
				if x > tmp {
					fmt.Println("great")
					insert(tree, name, x)
				} else {
					fmt.Println("bad")
				}
			} else {
				fmt.Println("great")
				insert(tree, name, x)
			}
		}
	}
}

func insert(node *treeNode, name string, x float32) {
	for i := 0; i < len(name); i++ {
		idx := int32(name[i] - 'a')
		if node.next[idx] == nil {
			node.next[idx] = new(treeNode)
		}
		node = node.next[idx]
	}
	node.max = x
}

func searchAndStoreMax(node *treeNode, name string, x float32) float32 {
	for i := 0; i < len(name); i++ {
		idx := int32(name[i] - 'a')
		if node.next[idx] == nil {
			return -1
		}
		node = node.next[idx]
	}
	if x > node.max {
		tmp := node.max
		node.max = x
		return tmp
	}
	return node.max
}

結果又又又是超時，我服了，

終于發現問題

后來我又嘗試了很多方法都不行，比如懷疑是不是Go的map性能不行，換成Java試試，結果還是不行，

最后我在網上搜索牛客網時發現了一個突破口（對，沒錯，這次比賽是在牛客網上舉辦的），

簡單說，牛客網的ACM模式輸入可能需要讀入一行然后再自己處理成想要的資料，

抱著懷疑的態度我試了下，果然，淦！用最開始的map就能ac掉！雖然我也不知道這兩種輸入有什么區別，關鍵我還是用的網站上提示的輸入方式，確實太坑了，

正確的輸入方式如下：

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	var n int
	var name string
	var x float64
	input := bufio.NewScanner(os.Stdin)
	if input.Scan() {
		n, _ = strconv.Atoi(input.Text())
	}

	scores := make(map[string]float64, n)
	var max float64
	for i := 0; i < n; i++ {
		if input.Scan() {
			arr := strings.Split(input.Text(), " ")
			name = arr[0]
			x, _ = strconv.ParseFloat(arr[1], 32)
		}

		...
	}
}