BISHI47　交换到最大¶

简单通过率 43.74%python3样例通过牛客 AC贪心

讲解章节：贪心

一句话

每次把一个非首位、非 0 的字符减 1 后与左邻交换，求字典序最大串。

解题思路¶

这题考什么¶

先弄清一次操作的本质：某个字符向左移动一格，代价是自身数值减 1。要向左移 t 格，就得连做 t 次，每次动之前它必须非 0，即需要 d >= t，移动后变成 d - t（恰好 >= 0）。被它越过的那些字符只是被动右移一格，数值不变、不花任何代价。

所以最终串等价于：不断从「剩余字符序列」的前 10 个里挑一个放到答案末尾，挑走位于相对偏移 t 处的字符 d 时写下 d - t（t 只可能是 0..9，因为 d <= 9，t > 9 时 d - t < 0 不可行）。

贪心：逐位构造答案，每位取 d - t 的最大值；并列时取偏移 t 最小的那个 —— 因为选靠左的元素之后，夹在中间的那些元素的偏移会整体减 1，未来更便宜，是严格占优的选择。由于偏移 0 的元素给出 d - 0 >= 0，最大值恒非负，不会写出负数字符。

验算 "1709"：候选 1-0=1, 7-1=6, 0-2=-2, 9-3=6 -> 取 6（偏移 1，靠左）；剩 [1,0,9]：1, -1, 7 -> 取 7；剩 [1,0]：1, -1 -> 取 1；剩 [0] -> 0。得 "6710" ✓。

数据规模与复杂度¶

t <= 1e4，∑|s| <= 2e5。每输出一位只看长度 <= 10 的窗口，总复杂度 O(10 * ∑|s|) = 2e6，稳过。实现上维护一个最多 10 个元素的小缓冲 buf：取走某个元素后 del buf[best] 自动完成「后面的元素偏移 -1」，再从原串补足到 10 个。注意 O(n^2) 的「每次在完整列表里删除」在 |s| = 2e5 时会退化，不能那么写。

坑在哪¶

窗口大小是 10 而不是 9：偏移 t 的取值是 0..9，共 10 个位置；
并列时必须选最左边的，选最右会白白多花掉中间元素的未来预算（"1709" 里 7 和 9 都能给出 6，选 9 会让后面变差）；
首位字符不能被操作，但它可以被别人越过而右移 —— 这正是 "19" -> "81" 的原理，别误以为首位永远留在最前；
多组数据、字符串输入，整块 buffer.read().split() 即可（串内无空格）；
结果长度与原串相同：操作只是移动与减值，既不删字符也不加字符。首位只增不减 —— 答案第一位取的是 max(d - t)，而偏移 0 的候选正是原首位，所以不会出现前导零；但后面的位置完全可能是 0（"1709" -> "6710"）。

贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI47.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for idx in range(1, t + 1):
        s = data[idx]
        n = len(s)
        res = bytearray(n)             # 答案与原串等长：操作只搬运、不增删字符
        buf = []                       # 剩余字符的前若干个（最多 10 个）
        p = 0                          # 原串里下一个还没进过窗口的位置
        for j in range(n):
            # 把窗口补满 10 个：偏移只可能是 0..9，再远的字符搬不过来
            while len(buf) < 10 and p < n:
                buf.append(s[p] - 48)  # bytes 取出的是 ASCII 码值，减 48 得数字
                p += 1
            # 偏移 0 的字符不花代价，用它做初值，保证「并列时取最左」
            best = 0
            bv = buf[0]
            for k in range(1, len(buf)):
                v = buf[k] - k         # 移到当前位要走 k 步，代价 k
                if v > bv:             # 严格大于才换，并列时保留更左的候选
                    bv = v
                    best = k
            res[j] = bv + 48           # 数字转回 ASCII 码值写进结果
            del buf[best]              # 后面的元素偏移自动整体 -1
        out.append(res.decode())
    sys.stdout.write("\n".join(out) + "\n")


main()

BISHI47 交换到最大¶