首页 > 试题广场 >

队列最小修改

[编程题]队列最小修改

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

已知一个奇怪的队列，这个队列中有 n 个数，初始状态时，顺序是 1,2,3,4,…n，是 1-n 按顺序排列。这个队列只支持一种操作，就是把队列中的第 i 号元素提前到队首 (1<i<=n) ，如有 4 个元素，初始为 1，2，3，4 ,可以将 3 提前到队首，得到 3，1，2，4 。现在给出一个经过若干次操作之后的序列，请你找出这个序列至少是由原序列操作了多少次得到的。

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

输入描述:

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

输出描述:

输出仅包含一个数字，表示至少操作了几次

示例1

输入

5
5 2 1 3 4

输出

说明

按顺序把 2 和 5 提到队列前

算法知识视频讲解

JavaScript

小土豆不会掉头发

n=parseInt(readline());
let arr=readline().split(' ')
let a=[]
for(item of arr){
a.push(parseInt(item))
}
n--
while (n>0){
if(a[n]<a[n-1]){
console.log(n)
break
}
n--
}
if(n==0){
console.log(0)
}

发表于 2021-08-21 18:50:07 回复(0)

JavaScript

牛客793971400号

一看答案都是泪，是我想太多了，emm...

var lines=[]
while(line=readline()){
    lines.push(line)
}
var arr = [],
    n = parseInt(lines[0]),
    r = n - 1;
for (item of lines[1].split(' ')) {
    arr.push(parseInt(item))
}
for (let i = n-1; i >= 0; i--) {
    if (arr[i] > arr[i - 1]) {
        r--
    } else break
}
console.log(r)

发表于 2020-02-15 21:12:03 回复(0)