主題

ZeroJudge - e809: 1.字母排序 (Letters)　解題心得

Not In My Back Yard | 2020-03-06 00:02:44 | 巴幣 0 | 人氣 168

題目連結：

e809: 1.字母排序 (Letters)

題目大意：

第一列給定一字串，其包含 N （0 ＜ N ≦ 26）個不重複大寫字母，左至右代表字母的由小到大的順序。

第二列也給定一字串 S （1 ≦ |S| ≦ 5 × 10 ^ 6 個大寫字母），代表要排序的字串（按照第一列給定的順序排序字母）。

第三列給定一正整數 Q ，代表有 Q 筆詢問。接著的 Q 列輸入，每列給定一正整數 X （1 ≦ X ≦ |S|），試問排序後第 X （字串索引值從左到右，並從 1 開始）個字母為何？

範例輸入：

範例輸入一：

CBA

ABCABCABC

4

2

1

5

8

範例輸入二：

ZAD

ZZZZZAAAADDD

3

1

6

12

範例輸出：

範例輸出一：

C

B

A

範例輸出二：

Z

A

D

解題思維：

直接寫一個排序，把原有的字串從原本的順序變成按照給定的大小順序去排序當然是可以的。

但是也可以學習計數排序法（Counting Sort）的精神，去統計每個種類的字母。然後令一變數 Y，先加上第一順位的字母之數量，然後看看 Y 有無 ≧ X。有就輸出第一順位的字母（因為表示第 X 個字母含括在這 Y 的字母裡）；反之，加上第二順位的字母之數量，再看看有無 ≧ X 。有就輸出第二順位的字母……以此類推。

本人的程式碼（於 CodePile 上）

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

#程式題目解題心得