首页 > 试题广场 >

排序次数

[编程题]排序次数

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

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数数组 $\{a_1,a_2,\dots,a_n\}$ 。小摩希望将数组调整为单调不减的顺序，即满足 $a_1 \leqq a_2 \leqq\dots \leqq a_n$ 。
$\hspace{15pt}$ 他只能重复进行以下操作：
${\hspace{20pt}}_\texttt{1.}\,$ 任选一个下标 $i\,\left(1\leqq i\leqq n\right)$ ；

${\hspace{20pt}}_\texttt{2.}\,$ 将元素 $a_i$ 从当前位置删除，并插入到数组的末尾（其余元素的相对顺序保持不变）。

$\hspace{15pt}$ 请你求出使数组变为严格递增所需的最少操作次数。

输入描述:

第一行输入一个整数  表示数组的长度。 
第二行输入  个整数  表示数组元素。

输出描述:

在一行上输出一个整数，代表最少操作次数。

示例1

输入

4
19 7 8 25

输出

说明

对于第一组样例： 
第一次操作，将  移动到末尾，数组变为 ； 
第二次操作，将  移动到末尾，数组变为 ，此时数组严格递增。 
因此答案为 。

算法知识视频讲解

bandiaoz

发表于 2024-12-18 16:23:34

解题思路这道题可以转化为最长上升子序列(LIS)问题：每次移动一个数到末尾，实际上是在寻找原序列中的一个上升子序列不需要移动的数必然形成一个上升子序列因此，需要移动的次数 = 序列长度 - 最长上升子序列的长度例如对于序列 [19, 7, 8, 25]：最长上升子序列是 [7, 8 展开全文

勤奋努力的查理一定要上岸

发表于 2024-10-08 21:35:46

import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class 展开全文