首页 > 试题广场 >

交换到最大

[编程题]交换到最大

热度指数：2407 时间限制：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

输入

输出

说明

以  为例：
   ；
   ，得到答案 。

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

算法知识视频讲解

Java

BraveCoder

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine(); // 处理换行符
        
        while (n-- > 0) {
            // 读取字符串并转为整数数组
            char[] chars = in.nextLine().toCharArray();
            int[] s = new int[chars.length];
            for (int i = 0; i < chars.length; i++) {
                s[i] = chars[i] - '0';
            }

            boolean flag = true;
            // 循环执行操作直到无法继续
            while (flag) {
                flag = false;
                // 从右向左执行一***作
                for (int i = s.length - 1; i > 0; i--) {
                    // 满足差值≥2时交换并减1
                    if (s[i] - s[i - 1] >= 2) {
                        int tmp = s[i];
                        s[i] = s[i - 1];
                        s[i - 1] = tmp - 1;
                    }
                }
                // 检查是否还能操作
                for (int i = s.length - 1; i > 0; i--) {
                    if (s[i] - s[i - 1] >= 2) {
                        flag = true;
                        break;
                    }
                }
            }
            
            // 输出结果
            for (int i : s) {
                System.out.print(i);
            }
            System.out.println();
        }
    }
}

发表于 2025-09-04 09:50:52 回复(0)

Python3

牛客341639822号

n = int(input()) for _ in range(n):
    st = list(map(int, input())) while True: for i in range(1, len(st)): if st[i] - st[i - 1] >= 2:
                tmp = st[i]
                st[i] = st[i - 1]
                st[i - 1] = tmp - 1  if all(st[i] -st[i-1]<2 for i in range(1, len(st))): break  print(''.join(map(str, st)))

发表于 2025-10-04 17:23:45 回复(0)

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)

草海桐

从左往右遍历，每次在右边[i+1, Min(len-1,i+8)]范围内找最合适的位置

package main

import (
    "fmt"
)

func Min(a, b int) int{
    if a < b{
        return a
    }
    return b
}

func main() {
    var t, length, max_id int
    var s string
    fmt.Scanf("%d", &t)
    for t > 0{
        t--
        fmt.Scanf("%s", &s)
        b := []byte(s)
        length = len(b)
        for i:=0;i<length;i++{
            if b[i] > '7'{ // '8'和'9'不需要操作
                continue
            }
            max_id = i
            for j:=i+1;j<=Min(length-1, i+8);j++{
                if b[j]-byte(j-i) > b[max_id]-byte(max_id-i){ // 差值
                    max_id = j
                }
            }
            if max_id > i{
                for max_id >i {
                    b[max_id], b[max_id-1] = b[max_id-1],b[max_id]-1
                    max_id--
                }
            }
        }
        fmt.Println(string(b))
    }
}

发表于 2025-09-07 13:51:48 回复(0)

提交观点

问题信息

贪心

难度：

4条回答 49收藏 571浏览

交换到最大

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题