沙滩按照线型摆放着n个大小不一样的球形石头，已知第i 个石头的半径为ri，且不存在两个石头有相同的半径。为了使石头的摆放更加美观，现要求摆放的石头的半径从左往右一次递减。因此，需要对一些石头进行移动，每次操作可以选择一个石头，并把它放在剩下n- 1个石头在最左边或最右边。问最少需要操作多少次才能将这n个石头的半径变成升序？
样例输入：
5
4 1 2 5 3
样例输出：
2
思路： 实则题目就等于求出最长升序子字符串，但因为题目加了限制条件：每次可选择一块石头，并把它放在剩下n-1块石头的最左边或最右边。并且不存在两个石头有相同的半径，且1<=ri<=n，所以每个石头的半径正好为1到n的整数。所以转变为需要我们去求出最长真升序子字符串，即升序子字符串的相邻元素之间相差1。比如3 2 1 4 6 5，排完序后：1 2 3 4 5 6，对比两个子字符串，发现原字符串3 4 5排完序相对位置没变，所以3 4 5即为原字符串的最长真升序字符数组。找到最长真升序字符数组后，剩下有多少个其他字符就应该挪动多少次。
代码：
#include<bits/stdc++.h> using namespace std; int main() { int num = 1, max = 1; int n; cin>> n; vector<int> vec(n); vector<int> vec2(n); int tmp; for(int i = 0; i < n; ++i){ cin>> tmp; vec[i] = tmp; } for(int i = 0 ; i < n; ++i){ vec2[i] = vec[i]; for(int j = i + 1; j <n; ++j){ vec2[j] = vec[j]; if(vec2[i] + 1 == vec2[j]){ num += 1; vec2[i] = vec2[j]; } } if(num > max){ max = num; } num = 1; } cout<< n - max; return 0; }