題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟠 P14357 [CSP-J 2025] 拼数

Problem Statement

題目簡述

給定一個只包含小寫英文字母與數字的字串。可以使用其中任意多個數字，且每個位置的數字最多使用一次，將選出的數字任意重排後拼成一個正整數。

求所有能拼出的正整數中的最大值。

Constraints

約束條件

  • 字串僅包含小寫英文字母與數字。
  • 字串中至少包含一個 11 到 99 的數字，因此答案一定是正整數。

思路：貪心

由於在末尾加任何數字只會讓數值變大，因此使用所有數字一定是最優的。

接著考慮數字的排列順序。對於一個正整數，高位的權重最大，因此應該將數字按從大到小的順序排列。

不過數字只有 1010 種，不需要排序，統計頻率後按降序展開即可做到 O(n+D)\mathcal{O}(n + D)。

複雜度分析

  • 時間複雜度：O(n+D)\mathcal{O}(n + D)，其中 nn 是字串長度，DD 是數字的種類數（這裡是 1010）
  • 空間複雜度：O(1)\mathcal{O}(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solve():
    s = input().strip()

    cnt = [0] * 10
    for c in s:
        if c.isdigit():
            cnt[ord(c) - ord("0")] += 1

    ans = []
    for i in range(9, -1, -1):
        ans.append(str(i) * cnt[i])
    print("".join(ans))


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @4AUB. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.