首页 > 试题广场 >

队列最小修改

[编程题]队列最小修改

热度指数：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 提到队列前

算法知识视频讲解

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)

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)