样例过,第二个点就错。。。
思路:维护前缀代价 pre,后缀代价 suf,求 (prei+sufi+1)min。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
void IOS()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void file(string file_name)
{
freopen((file_name+".in").c_str(),"r",stdin);
freopen((file_name+".out").c_str(),"w",stdout);
}
int t,n,a[200010],pre[200010],suf[200010];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
pre[1]=suf[n]=0;
if(n==1||n==2)
{
cout<<0<<'\n';
return ;
}
for(int i=2;i<n;i++)
{
pre[i]=pre[i-1]+(a[i-1]<a[i]);
}
for(int i=n-1;i>1;i--)
{
suf[i]=suf[i+1]+(a[i]<a[i+1]);
}
int ans=9e18;
for(int i=1;i<n;i++)
{
ans=min(ans,pre[i]+suf[i+1]);
}
cout<<ans<<'\n';
}
signed main()
{
//IOS();
//file("");
cin>>t;
while(t--)solve();
return 0;
}