首页 > 试题广场 >

最小排列

[编程题]最小排列

热度指数：2130 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

由数字 1 到 n 组成的一个序列我们称为一个 n 排列。对于两个不同的 n 排列 𝐴 = 𝑎1𝑎2 ... 𝑎𝑛 和 𝐵 = 𝑏1𝑏2 ... 𝑏𝑛 我们可以按字典序比较他们的大小:从前往后找到第一个两个排列中数字不同的位置，即找到一个位置𝑝使得 𝑎1 = 𝑏1 , 𝑎2 = 𝑏2 , ... , 𝑎𝑝−1 = 𝑏𝑝−1 , 𝑎𝑝 ≠ 𝑏𝑝 ，若 𝑎𝑝 < 𝑏𝑝 ，我们则称排列 𝐴 小于排列 𝐵 ，反之则 𝐴 大于 𝐵 。现在给出一个 n 排列，你需要选择排列中的两个不同的位置，然后交换这两个位置的数字，你需要使得最后得到的排列尽量小。注意你必须进行一次且只能进行一次操作。

数据范围： $2 \le n \le 10^5 , 1 \le a_i \le 10^5\$

输入描述:

第一行包含一个数字 𝑛 ，表示排列的长度。
第二行包含 𝑛 个数字构成一个 𝑛 排列。

输出描述:

输出一个 n 排列，表示能得到的最小的排列。

示例1

输入

3
3 2 1

输出

1 2 3

示例2

输入

4
2 1 4 3

输出

1 2 4 3

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([]int,n)
    pre,cur:=-1,-1
    for i:=0;i<n;i++{
        fmt.Fscan(in,&arr[i])
        if pre==-1{
            if arr[i]!=i+1{
                pre=i
            }
        }else{
            if arr[i]==pre+1{
                cur=i
            }
        }
    }
    if pre==-1{
        arr[n-2],arr[n-1]=arr[n-1],arr[n-2]
    }else{
        arr[pre],arr[cur]=arr[cur],arr[pre]
    }
    for _,x:=range arr{
        fmt.Printf("%v ",x)
    }
}

发表于 2023-03-18 10:44:41 回复(0)