已知一个奇怪的队列,这个队列中有 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.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); } } }
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)
#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; }
""" 利用后半部分已排序的性质,由后往前遍历,遇到不是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)
#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; }
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); } }
还行吧,比较简单,统计最长的正序序列长度,再利用:队列长度-最长的正序序列长度-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)); }
/*** * * * * */ 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