切換
舊版
前往
大廳
主題

ZeroJudge - e544: 00612 - DNA Sorting 解題心得

Not In My Back Yard | 2019-11-26 20:28:25 | 巴幣 2 | 人氣 409

題目連結:


題目大意:
給定一正整數 T ,代表有 T 筆的測試資料。每筆測資開頭有一列空白列,接著的一列給定兩正整數 n 、 m (n ≦ 50 , m ≦ 100),代表接下來有 m 列輸入、每列輸入給定一長度為 n 的字串(字串只包含大寫字母)。

現在定義一種度量「反轉」(inversions),代表字串的排序程度。「反轉」的值為對於字串裡每個字元,在字典序上大於多少個位於其右邊的字元。

例如字串 DAAEBC ,D 大於 A 、 A 、 B 、 C 四個字元,而 E 大於 C 。因此,此字串的「反轉」為 5 。

請將給定的 n 個字串以反轉度量小到大排序(也就是從較有排序的字串到較無排序的字串)。如果兩字串反轉的度量相等,則以輸入的順序排序。



範例輸入:
1

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT


範例輸出:
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA


解題思維:
用一個結構(Struct)把字串的內容、輸入的順序以及其反轉度量都存起來。反轉度量的求法單純就是以看每個位置大於幾個右邊的字元,把數量全部加起來即可獲得。

接著就是依據題目的條件排序即可。

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

創作回應

更多創作