【排序最少操作数，最长子序列】MT笔试

题目：

给一个n个数的排列，n的数的范围为1~n且各不相同，比如[3,1,2]为一个3个数的排列。
现在要求对这个无序的n个数的排列，排成一个递增序列，但只能进行一种操作：从n个数中任选两个数，大的放最后一位，小的放第一位，问最少进行多少次这种操作，n个数的排列最终变成一个递增序列。
例如[1,5,4,2,3]，最少需要2次这种操作(第一次选4和2，2放第一位，4放最后一位，变成[2,1,5,3,4]；第二次选1和5，变成[1,2,3,4,5]，需要2次操作)

输入为n个数，数和数之间用空格隔开，输出最少的操作次数。

示例输入：
1 5 4 2 3
输出：
2

思路：

从头遍历这个数组，建立一个辅助数组存储 当前元素作为尾的、最长递增为 1 的子序列长度；那么前有（当前数 - 长度）个数，后有（n - 当前数）个数，选择这两个数中最大的数为操作数；

遍历完整个数组后找到最少的操作数（可以知道 n/2 为默认最多的操作次数）

 1 #include <iostream>
 2 #include <vector>
 3 #include <sstream>
 4 #include <string>
 5 
 6 using namespace std;
 7 
 8 int LIS(vector<int>v)
 9 {
10     int cmp = v.size() / 2; //最多排 n/2 次
11     int count = v.size();   //总共有多少个数
12     vector<int>assist(count, 1);    //辅助数组，存储最长递增为1的子序列长度(可以不连续，但是公差必须为1)
13     for (int i = 1; i < count; i++) {
14         for (int j = 0; j < i; j++) {
15             if (v[i] == v[j] + 1) { //是递增为1的子序列
16                 assist[i] = assist[j] + 1;
17                 int cmp2 = max(v[i] - assist[i], count - v[i]); //以v[i]为尾的子序列，前面有多少数，后面有多少数，选最大的那个
18                 cmp = min(cmp, cmp2);   //与当前最小的排序次数作比较
19             }
20         }
21     }
22     return cmp;
23 }
24 
25 int main() {
26 
27     string input;
28     getline(cin, input);
29 
30     istringstream iss(input);
31     int num;
32     vector<int>numbers;
33     while (iss >> num) {
34         numbers.push_back(num);
35     }   //此时输入的数字已经处理完毕
36 
37     int result = LIS(numbers);
38     cout << result << endl;
39 
40     return 0;
41 }

(〃＞＿＜;〃)(〃＞＿＜;〃)(〃＞＿＜;〃)