zoj1423的Python解答

zoj1423是一道比较典型的贪心算法题目。这道题目要求我们给定一个由数字组成的字符串，将其中一些数字改为字母，使得改变后的字符串能够按照字典序最小的方式排列。

下面是Python的解答：

s = input().strip()
ans = [s]
for i in range(1, len(s)):
    if s[i] < ans[-1]:
        for j in range(len(ans)-1, -1, -1):
            if s[i] >= ans[j]:
                ans[j] = s[i]
                break
        else:
            ans.insert(0, s[i])
    else:
        ans.append(s[i])
print(''.join(ans))

该解答通过贪心策略，从左到右扫描字符串，对于每一个数字，如果它小于当前已经构建好的字母串的最后一个字符，则从后往前找到第一个比它小的字符并替换掉，否则直接加入字母串末尾。这样得到的字母串即为字典序最小的排列方式。