题解 | #九小时九个人九扇门#

定义一个f数组: 当a[i]>=m时,f[i]=1; 当a[i]<m时,f[i]=-1; 然后求一下f数组的总和sum,如果sum<=0,那就是-1,否则就是sum的值.

可知如果定义一个f数组的前缀和.若f[k]>=1,那么说明1-k这段的中位数一定是≥m的; 同样如果f[b]-f[a]>=1(b>a),那么说明a-b这段的中位数一定≥m.那么对于如果f数组的总和为sum(sum>=1),说明f数组中可以分成sum段,其中每段的和为1.所以答案就是sum.

using namespace std;
const int maxn=1e5+50;
int n,m;
int a[maxn];
int f[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        memset(f,0,sizeof(f));
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            if(a[i]>=m) f[i]=1;
            else f[i]=-1;
        }
        for(int i=1;i<=n;i++) f[i]=f[i-1]+f[i];
        if(f[n]>=1) cout<<f[n]<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}