C++ 算法题解

排序操作次数

题目描述:
有一种排序算法定义如下，该排序算法每次把一个元素提到序列的开头，例如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");
}