首页 > 试题广场 >

交换到最大

[编程题]交换到最大

热度指数：2426 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个仅由数字 $\texttt{0-9}$ 构成的字符串 $s$ 。一次操作可按如下方式进行：
$\hspace{23pt}\bullet\,$ 从 $s$ 中选择既不是最左端字符也不为 $\texttt{0}$ 的某一字符；
$\hspace{23pt}\bullet\,$ 将该字符的数值减少 $1$ ；
$\hspace{23pt}\bullet\,$ 随后把它与左侧相邻字符交换位置。

$\hspace{15pt}$ 例如，字符串 $\texttt{$ 经过一次操作可以变成 $\texttt{$ 或 $\texttt{$ 。

$\hspace{15pt}$ 你可以不限次数地执行上述操作。请计算能够得到的字典序最大的字符串，并输出该字符串。

输入描述:

第一行输入一个整数 ，表示测试用例数量。
此后  行，每行输入一个不含前导零的数字字符串 ，满足 。
保证所有测试用例的  之和不超过 。

输出描述:

对于每个测试用例，在一行上输出通过任意次数操作后能够得到的字典序最大的字符串。

示例1

输入

输出

说明

以  为例：
   ；
   ，得到答案 。

再以  为例，可按如下序列操作：
   ；
   ；
   ，最终得到答案 。

算法知识视频讲解

JavaScript V8

xuwzen

思路：从右往左遍历字符串，判断右边字符数值-1后仍然大于左边字符就执行操作。如果某一轮扫描没有发生操作就标记整个过程结束。

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    const t = Number(await readline());
    const cases = Array(t);
    for (let i = 0; i < t; i++) {
        let s  = await readline();
        let arr = s.split('').map(Number);
        const n = arr.length;
        // console.log(arr)
        while (true) {
            let stop = true;
            for (let i = n-1; i > 0; i--) {
                if (arr[i-1] < arr[i] - 1) {
                    arr[i]--;
                    [arr[i-1], arr[i]] = [arr[i], arr[i-1]];
                    stop = false;
                }
            }
            if (stop) {
                break;
            }
        }

        console.log(arr.join(''));
    }



}()

发表于 2025-09-29 12:23:48 回复(0)

提交观点

问题信息

贪心

难度：

1条回答 49收藏 579浏览

交换到最大

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题