ETH官方钱包

前往
大廳
主題

ZeroJudge - a528: 大數排序 解題心得

Not In My Back Yard | 2021-08-15 00:00:03 | 巴幣 0 | 人氣 491

題目連結:


題目大意:
輸入有多筆測試資料。每筆測資第一列給定一正整數 N(0 < N < 1000),代表接著有 N 列輸入,每列給定一整數(其絕對值 ≦ 10 ^ 100)。請將這 N 個整數由小排到大後輸出。



範例輸入:
5
1
3
2
5
0
4
222222222222222222222222222
111111111111111
-44444444444444444444444444444444444444444444444444444
33333333333333333333333333333333333333333333


範例輸出:
0
1
2
3
5
-44444444444444444444444444444444444444444444444444444
111111111111111
222222222222222222222222222
33333333333333333333333333333333333333333333


解題思維:
雖然對於 Python 那種內建大數的語言,這題就是直接轉成整數排序即可。但是對於 C++ 等沒有內建大數之語言,則需要將這些整數存成字串,然後想辦法自定義排序。

那麼整數們之間是怎麼比較的呢?

可以看到負數應排於正數前,所以看到 '-' 開頭的整數應排於所有不以 '-' 開頭的整數「前面」。

而對於同樣是正數的兩個數字。當有一者位數比較長時,也就代表該數比較大,因此該數應排於另一數「之後」;而相同長度便可以按照一般字串字典序去排。如 "1024" 、 "2776" 等等這種相同長度的數字是可以藉由字典序比出數字大小的,此例中 "1024" < "2776"。

而負數則類似於正數,不過「結論」是相反的。當有一者位數比較長時,也就代表該數負得比較多,因此應排於另一數「之前」;而相同長度應按字典序倒序來排。如 "-1024" 、 "-2776","-1024" < "-2776" 所以 "2776"(絕對值)比較大,也就是說 "-2776" 是比較小的。



剩下的部分就是跟其他自定義排序的題目類似(如這題)即可以完成排序。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作