首页 > 试题广场 >

队列最小修改

[编程题]队列最小修改
  • 热度指数：5905 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
已知一个奇怪的队列，这个队列中有 n 个数，初始状态时，顺序是 1,2,3,4,…n，是 1-n 按顺序排列。这个队列只支持一种操作，就是把队列中的第 i 号元素提前到队首 (1<i<=n) ，如有 4 个元素，初始为 1，2，3，4 ,可以将 3 提前到队首，得到 3，1，2，4 。 现在给出一个经过若干次操作之后的序列，请你找出这个序列至少是由原序列操作了多少次得到的。

数据范围：

输入描述:
第一行是一个整数n(1<=n<=10^5)，表示序列中数字的数量。 接下来一行有n个数，是1-n的一个全排列。数字之间用空格隔开。


输出描述:
输出仅包含一个数字，表示至少操作了几次
示例1

输入

5
5 2 1 3 4

输出

2

说明

按顺序把 2 和 5 提到队列前
算法知识视频讲解
开通博客
头像 重生之我要当分子
发表于 2025-01-01 15:05:17
解题思路 这是一个序列操作问题。通过观察可以发现，从后向前看，如果序列是递增的，那么这部分不需要操作。 关键点： 从后向前看，递增序列不需要操作 遇到第一个递减位置时停止 前面的元素都需要移动到队首 算法步骤： 从后向前遍历序列 统计末尾的递增序列长度 剩余的元素数量就是最少操作次数 代码 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 动态规划 数组 前端工程师 队列 京东 2019 查找
上传者：小小
难度：
29条回答 11168浏览

热门推荐

通过挑战的用户

查看代码

相关试题

队列最小修改

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号