原题链接

经过若干组数据发现贪心可行性后试图证明

请移步

code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,ans=0;
        cin>>n;
        int x=2e9,y=3e9;
        for(int i=1;i<=n;i++)
        {
            int a;
            cin>>a;
            if(x<y)swap(x,y);
            if(a>x)y=a,ans++;
            else if(a>y)x=a;
            else y=a;
        }
        cout<<ans<<endl;
    }

    return 0;
}