题目大意:
给你一个序列,问最少去掉多少个前缀元素能得到一个“好序列”。“好序列”是这样定义的:每次能从一个序列的左右两边取数,若能取出一个非递减序列则是“好序列”。
思路:
先分析什么样的序列能够叫做好序列,首先假设这个序列是b1,b2,…bm…bn。那么bm一定是最大的元素,然后从左到右是非减序列,从bm到bn是非增序列。为什么呢,假设b2<b1.那么你无论怎么取数b2一定在b1的后面形成递减的趋势,这是不被允许的。所以我们思路也很明确了,因为是去掉前缀,所以我们就找最长“好序列”,从后往前找,找到第一个不满足从后往前递增条件的元素,然后从这个元素往前找找到开始升的那个元素就停止,最后答案就是n减去最长“好序列”长度。
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
int j=n-1;
while(j>0 && a[j-1] >= a[j]) j--;
while(j>0 && a[j-1] <= a[j]) j--;
cout<<j<<endl;
}
//system("pause");
}