题目描述: 有一种排序算法定义如下,该排序算法每次把一个元素提到序列的开头,例如2, 1, 3, 4,只需要一次操作把1提到序列起始位置就可以使得原序列从小到大有序。现在给你个乱序的1-n的排列,请你计算最少需要多少次操作才可以使得原序列从小到大有序。 输入描述
输入第一行包含两个正整数n,表示序列的长度。(1 <= n <= 100000) 接下来一行有n个正整数,表示序列中的n个元素,中间用空格隔开。(1 <= a_i <= n)
输出描述
输出仅包含一个整数,表示最少的操作次数。
样例输入 4 2 1 3 4
样例输出 1
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
int get_operation_count(const std::vector<int>& vec) {
std::vector<int> sorted(vec);
std::sort(sorted.begin(), sorted.end());
int p = sorted.size() - 1;
int q = p;
while (p >= 0 && q >= 0) {
if (vec.at(p) == sorted.at(q)) {
--p;
--q;
} else {
while (p >= 0 && vec.at(p) != sorted.at(q)) {
--p;
}
}
return q + 1;
}
}
int main() {
int n = 0;
std::cin >> n;
std::vector<int> vec(n);
for (int i = 0; i < n; ++i) {
std::cin >> vec.at(i);
}
std::cout << get_operation_count(vec) << std::endl;
system("pause");
}