首页 > 试题广场 >

队列最小修改

[编程题]队列最小修改

热度指数：5929 时间限制：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 。现在给出一个经过若干次操作之后的序列，请你找出这个序列至少是由原序列操作了多少次得到的。

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

输入描述:

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

输出描述:

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

示例1

输入

5
5 2 1 3 4

输出

说明

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

算法知识视频讲解

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    int res=n-1;
    for(int i=n-1;i>0;i--)
    {
        if(num[i]>num[i-1])
            res--;
        else 
            break;
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-08-21 19:50:46 回复(2)

Java

lmz9509

/*
参考其他人：应该是找最后一个升序数组的起始下标，一个元素可以修改任意次
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main{
    public static void main(String[] args)throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0;i<n;i++)
            arr[i] = Integer.parseInt(str[i]);
        if(n==1)//防止长度不够的情况
            System.out.println(0);
        else
            for(int i = arr.length - 1;i>0;i--){
            if(arr[i] < arr[i-1]){
                System.out.println(i);
                break;
            }else if(i==1)//防止没有变换的情况
                System.out.println(0);
        }
    }
}

发表于 2020-05-23 13:19:05 回复(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)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n],r=n-1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=n-1;i>0;i--)
        if(a[i]>a[i-1])
            r--;
        else
            break;
    cout<<r<<endl;
    return 0;
}

发表于 2019-11-05 11:48:22 回复(0)

LongXiaJun

"""
利用后半部分已排序的性质，由后往前遍历，遇到不是nums[i] < nums[i-1]输出i即可
"""

n = int(input().strip())
nums = list(map(int, input().strip().split()))
ans, i , j =  0, 0, 0

if len(nums) <= 1:
    print(0)
    exit()

for i in range(n-1,1, -1):
    if nums[i] < nums[i-1]:
        print(i)
        exit()

print(0)

发表于 2019-08-01 18:02:13 回复(0)

小蝌蚪666

#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        cin>>v[i];
    }
    for(int i = n-1; i > 0; --i){
        if(v[i]<v[i-1]){
            cout<<i<<endl;
            return 0;
        }
    }
    //退出循环条件：n为1或者整个数组是升序的
    cout<<0<<endl;
    return 0;
}

把数组分成两部分：前半部分front是无序，后半部分back为升序队列，以n=4为例

初始状态：front={}为空，back={1,2,3,4}按照严格升序

操作数3：front={3}，back={1,2,4}

操作数2：front={2,3}，back={1,4}

...

每一次操作都是从back里面随意拿一个数放到front，操作之后back仍为有序的，且数目每次减1，所以从数组末尾检查看降序排列的back数组个数s，n-s即为最小操作次数

发表于 2019-08-23 15:15:46 回复(0)

infiniteft

思路：

从前到后，寻找最后一个升序序列的起始下标即可

#include<iostream>
#include<vector>

using namespace std;
int findMinOper(vector<int> &nums)
{
    int n = nums.size();
    int numOfOp = 0;
    for(int i = n - 1; i > 0 ;i -- )
    {
        if(nums[i-1] > nums[i])
        {
            numOfOp = i;
            break;
        }
    }
    return numOfOp;
}

int main(void)
{
    int n, num;
    vector<int> nums;
    cin >> n;
    do
    {
       cin >> num;
       nums.push_back(num);
    }while(--n > 0);
    cout << findMinOper(nums) << endl;
}

编辑于 2019-11-04 20:12:00 回复(0)

zpjzgz

直接求最小值的下标，如果不等于0，下标就是最小次，

如果等于0，因为有先决条件，1<i<=n，所以排除数组没有变动，剩下的就只能是全都动了一次，次数就是n。

最后此题最好加一个条件，每个元素只能调动一次，不然无法判断的。

发表于 2019-09-30 13:25:48 回复(2)

chist

let num = readline();
let arr = readline().split(' ');
for(var i = arr.length-1;i>0;i--){
    if(parseInt(arr[i])<parseInt(arr[i-1])){
        print(i);
        break;
    }
}
if(i==0){
    print(0);
}

发表于 2019-09-06 16:33:08 回复(0)

Java

牛客217455925号

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int t = 0;t<n;t++){
            int value = in.nextInt();
            arr[t] = value;
        }
        int i = 0;
        for(i = arr.length-2;i>=0;i--){
            if(arr[i+1]<arr[i]){
                break;
            }
        }
        int result = i+1;
        System.out.println(result);
    }
}

发表于 2023-03-11 15:05:04 回复(0)

忘魂儿

从后往前，只要后者比前者小，那么结果就是后者的下标

发表于 2022-01-27 21:43:54 回复(0)

牛客538022010号

const size = readline(),
arr = readline().split(' ');

for(let i = arr.length-1;i>=0;i--){
if(~~arr[i]<~~arr[i-1]){
console.log(i);
break;
}
if(i==0){
console.log(0)
}
}

发表于 2021-11-01 16:35:29 回复(0)

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)

小宇点

牛客的编程题怎么提交啊我用js提交的代码，数组该怎么表示，每次带数组就一直错。。。

发表于 2020-04-30 23:19:43 回复(0)

讲原则的coder在人才库

还行吧，比较简单，统计最长的正序序列长度，再利用：队列长度-最长的正序序列长度-1
即可。
最长的正序序列里的元素可以理解为每一被移动过的元素。

#include
int main(){
    int n,i,sq[100001],count;
    scanf("%d",&n);
    for(i = 0 ; i<n ; i++){
        scanf("%d",&sq[i]);
    }
    for(i = 0 ,count = 0; i < n-1 ; i++){
        if(sq[i+1] > sq[i]){
            count++;
        }else{
            count = 0;
        }

    }
    printf("%d",(n - count-1));

}

发表于 2020-04-15 18:23:02 回复(0)

喜之郎酸酸

Scanner scan=new Scanner(System.in);
        int n =scan.nextInt();
        int t=n;
        int[]arry=new int[n];
        int[]arr=new int[n];

        for(int i=0;i<n;i++) {

            arr[i]=scan.nextInt();




        }
        int sum=0;
for(int i=t-1;i>=0;i--) {

            arry[i]=t;
            t--;




        }
        for(int i=0;i<n;i++) {

            if(arr[i]>=arry[i]&&i!=n-1) {

                sum++;




            }





        }

        System.out.println(sum);

发表于 2020-03-14 10:42:15 回复(0)

事情一件一件去处理

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)
}

在数组最后一个数开始判断，只要出现后一个数小于前一个数就输出n值

发表于 2019-08-30 15:52:03 回复(0)

萧萧渐引风001

n = int(input())
arr = list(map(int, input().split()))

n -= 1
while n>0:
    if arr[n]<arr[n-1]: #从后往前查找，直到前一个元素比该元素大，输出n
        print(n)
        break
    n -= 1
if not n: #如果有序，或者n=1
    print(0)

发表于 2019-08-28 09:23:53 回复(0)

assmdx

/***
 *
 *
 *
 * */
var readline = require('readline')
 
const rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout
})
let isArr = false
let n = -1
rl.on('line',function(line) {
    if(!isArr) {
        n = parseInt(line)
        isArr = true
    } else {
        let arr = line.split(" ").map(v => parseInt(v))
        if(arr.length === 1) {
            console.log(0)
            isArr = false
            return
        }
        let j = arr.length - 1
        let now  = arr[j]
        let count = 0
        while(j >= 0 && now >= arr[j]) {
            count++
            now = arr[j]
            j--
        }
        console.log(arr.length - count)
        isArr = false
        return
    }
})
rl.on('close',function() {
    process.exit()
})
 
// 2 6 1 3 4 5
//   4 2 3 1 5
//  2 1
// 1 2

发表于 2019-08-24 15:04:09 回复(0)