首页 > 试题广场 >

最小排列

[编程题]最小排列

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

由数字 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

算法知识视频讲解

bao_hu_yuan_zhang

发表于 2024-03-22 21:36:43

#include <ios> #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n=0; 展开全文

17c89

发表于 2024-02-05 10:52:38

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

中科院在逃院士

发表于 2021-07-14 14:27:31

import java.util.*; public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int 展开全文

laglangyue

发表于 2020-06-26 21:46:31

用优先级队列保存正确顺序，如果存在有一个不在正确顺序上就往后找它在哪，然后交换值得注意的是，如果全部都在正确的顺序，即原排列时一个递增数列，那么也是要进行一次交换，交换最后两个 import java.util.PriorityQueue; import java.util.Scanner; pub 展开全文