首页 > 代码库 > 2017百度春招<有趣的排序>

2017百度春招<有趣的排序>

题目

度度熊有一个N个数的数组,他想将数组从小到大排好序,但是萌萌的度度熊只会下面这个操作:
任取数组中的一个数然后将它放置在数组的最后一个位置。
问最少操作多少次可以使得数组从小到大有序?

 

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int n, i, j;
    vector<int> a;
    vector<int> b;
 
    cin >> n;
    for(i=0; i<n; i++){
        int x;
        cin >> x;
        a.push_back(x);
        b.push_back(x);
    }
    sort(b.begin(), b.end());
    for(i=0; i<n; i++){
        if(a[i]==b[0])
            break;
    }
    for(i=0,j=0; i<n; i++){
        if(a[i]==b[j]){
            j++;
        }
        if(j==n) break;
    }
    cout << n-j;
 
    return 0;
}

 

2017百度春招<有趣的排序>