D. Digital string maximization 题解

一、题目核心规则理解

我们有一串数字，允许执行任意次操作：

1. 选一个非 0、非最左的位置 $j$
2. 把 $s[j]$ 减 1
3. 把它和左边的 $s[j-1]$ 交换

目标：得到字典序最大的字符串。

二、关键观察（解题突破口）

1. 操作本质

一个数字 $d$ 在位置 $j$，想要向左移动 $k$ 步到位置 $i = j-k$：

• 每左移 1 步，必须减 1
• 最终到达 $i$ 时，数值变为：$$d' = d - k$$
• 移动步数 $k$ 最多只能是 $\boldsymbol{d}$ 步（不能变成负数）

2. 贪心策略

要字典序最大，必须从左到右逐位最大化：

• 对第 $i$ 位，我们只需要在右边最多 9 位里找一个能移过来的最大可能值
• 因为数字最大是 9，最多只能减 9，所以只需要检查右边 10 位（$i+1$ ~ $i+10$）

三、算法流程

1. 遍历每一位 $i$，尝试让这一位尽可能大
2. 在 $i+1$ 到 $\min(i+10, n-1)$ 范围内找最优位置 $pos$： 使得 $s[pos] - (pos-i)$ 最大
3. 把 $pos$ 位置的数字一步步左移到 $i$，每一步减 1 并交换
4. 处理完当前位后，继续处理下一位

四、完整 AC 代码 + 注释

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int T;

void solve() {
    string s;
    cin >> s;
    int n = s.size();

    // 从左到右，逐位构造最大字典序
    for (int i = 0; i < n; i++) {
        int best_val = s[i];  // 当前最优值
        int best_pos = i;     // 最优来源位置

        // 只需要看右边最多 10 位（因为数字最多减9）
        for (int j = i + 1; j < min(n, i + 11); j++) {
            // 计算把 s[j] 移到 i 能得到的数值：s[j] - 步数
            int cur = s[j] - (j - i);
            if (cur > best_val) {
                best_val = cur;
                best_pos = j;
            }
        }

        // 把 best_pos 上的数字一步步左移到 i，每步减1
        for (int j = best_pos; j > i; j--) {
            swap(s[j], s[j - 1]);
            s[j - 1]--;  // 左移一步必须减1
        }
    }

    cout << s << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) solve();

    return 0;
}

五、代码细节解释

1. 为什么只遍历右边 10 位？

• 数字最大是 $9$，最多只能减 $9$
• 所以最多只能从 $i+9$ 位置移过来
• 循环写 min(n, i+11) 是安全范围

2. 核心公式

int cur = s[j] - (j - i);

表示：把 $j$ 位置的数字移动到 $i$，最终能变成多少。

3. 移动模拟

for (int j = best_pos; j > i; j--) {
    swap(s[j], s[j-1]);
    s[j-1]--;
}

严格模拟题目操作：左移一步 → 减 1。

六、复杂度分析

• 外层：$O(n)$
• 内层：最多 $10$ 次循环
• 总复杂度：$\boldsymbol{O(n \times 10)}$
• 完全可以通过 $n \le 2 \times 10^5$ 的极限数据

七、总结（最简版）

1. 贪心：从左到右，每一位尽量选最大
2. 范围限制：只看右边最多 10 位（数字最多减 9）
3. 操作模拟：找到最优数字，一步步左移并减 1
4. 高效：$O(10n)$，轻松通过大数据