题解
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
int map[100005];
vector<int> q;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
q.clear();
int answer=0;
int temp=0;
for(int i=1;i<=n;i++){
scanf("%d",&map[i]);
}
//找到不符合非递减的元素，存入q中
int before=map[1];
for(int i=1;i<n;i++){
if(map[i+1]<before){
q.push_back(map[i+1]);
}
else{
before=map[i+1];
}
}
//找到q中元素的最大值
int qlen=q.size();
int maxa=0;
for(int i=0;i<qlen;i++){
if(q[i]>maxa){
maxa=q[i];
}
}
//找到q中元素最大值有几个
for(int i=0;i<qlen;i++){
if(q[i]==maxa){
temp++;
}
}
//找到原序列中有多少个元素小于最大值
for(int i=1;i<=n;i++){
if(map[i]<maxa){
answer++;
}
}
printf("%d
",answer+temp);
}
return 0;
}
题意大概就是给出一个序列，每次可以把一个元素移动到序列顶部，问最少多少次可以形成一个非递减序列。
既然要形成非递减序列，那我们就先把不满足非递减的元素提取出来，我们需要把这些不满足要求的元素一个个提取到顶部，然后再把不符合要求的提到它的前面，这就涉及到一个问题，我们应该先提取不满足要求的元素中的哪个元素？
元素提取的顺序显然是影响最后结果的，下面看例子
7 8 1 2 3
在这个序列中，不满足要求的元素就是1 2 3，那么我们先动哪个元素呢？我们发现，如果先提取小的元素的话，比如把1提取到顶部，那么序列变成1 7 8 2 3，这时候再把2提取到顶部，变成2 1 7 8 3 ，这时1又不符合要求了，所以还要再把1提取到顶部，就算最后变成1 2 7 8 3 后，当把3提取到前面后，1和2还要再提取。而如果我们先提取大的，比如把3提取到顶部，变成3 7 8 1 2，那么下次再提取2时，直接提取就行了，显然提取大的元素的结果更优。
进而我们就发现，既然要先把不满足要求的元素中最大的提取到最前面，那么小于这个最大元素的元素都要再提取一次，比如
1 2 4 3
在这个序列中，不满足要求的元素只有3，我们把3提取到最顶端后，由于1 和2 小于3，所以1和2都要再移动一次。
现在我们知道小于这个最大元素的元素需要移动，那么等于最大元素的要不要移动呢？看例子
1 7 7 7 8 3 7 7
在这里，不满足要求的序列为3 7 7，最大元素为7 ，那么我们要把7移到最前面，由于不满足要求的序列中有两个7，所以我们都要把他们移到前面去，然后3也要移动，1也要移动，然后我们发现，在8前面的7 7 7似乎不用移动了，因为这时已经是1 3 7 7 7 7 7 8了，已经符合要求了，所以我们得出结论，只把不满足要求的序列中的最大元素移动，而在正常序列中的这个元素不移动。
那么我们的算法就确定了，首先找出不满足要求的元素，再找出这些元素中的最大值，然后统计总序列中小于这个最大值的元素有多少个，记为a，再统计不满足要求的元素中的最大元素有几个，记为b，那么答案就是a+b。