已知一个奇怪的队列,这个队列中有 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的一个全排列。数字之间用空格隔开。
输出仅包含一个数字,表示至少操作了几次
5 5 2 1 3 4
2
按顺序把 2 和 5 提到队列前
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); } }
/* 参考其他人:应该是找最后一个升序数组的起始下标,一个元素可以修改任意次 */ 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); } } }