首页 > 试题广场 >

队列最小修改

[编程题]队列最小修改
  • 热度指数:5827 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
已知一个奇怪的队列,这个队列中有 个数,初始状态时,顺序是 1,2,3,4,…n,是 1-n 按顺序排列。这个队列只支持一种操作,就是把队列中的第 号元素提前到队首 (1<i<=n) ,如有 个元素,初始为 1234 ,可以将 提前到队首,得到 3124 现在给出一个经过若干次操作之后的序列,请你找出这个序列至少是由原序列操作了多少次得到的。

数据范围:

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


输出描述:
输出仅包含一个数字,表示至少操作了几次
示例1

输入

5
5 2 1 3 4

输出

2

说明

按顺序把 2 和 5 提到队列前 
#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)
/*
参考其他人:应该是找最后一个升序数组的起始下标,一个元素可以修改任意次
*/
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)
一看答案都是泪,是我想太多了,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)
#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)
思路:
从前到后,寻找最后一个升序序列的起始下标即可

#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)
"""
利用后半部分已排序的性质,由后往前遍历,遇到不是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)
#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)
直接求最小值的下标,如果不等于0,下标就是最小次,
如果等于0,因为有先决条件,1<i<=n,所以排除数组没有变动,剩下的就只能是全都动了一次,次数就是n。
最后此题最好加一个条件,每个元素只能调动一次,不然无法判断的。
发表于 2019-09-30 13:25:48 回复(2)
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)
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)
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)
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)

还行吧,比较简单,统计最长的正序序列长度,再利用:队列长度-最长的正序序列长度-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)
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)
/***
 *
 *
 *
 * */
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)
n = int(input())
l = list(map(int, input().split()))
s = 1
for i in range(-2, -n - 1, -1):
    if l[i] < l[i + 1]:
        s += 1
    else:
        break
print(n - s)
发表于 2019-08-23 15:03:44 回复(0)