连续段的中数

最优解法

容易发现，答案是满足二分性质的。
二分答案，然后考虑怎么检查mid作为中数是否可行。
令所有大于等于mid的数字都为1，所有小于mid的数字都为-1，则相当于取一段长度大于等于k的数字使得数字和非负。用前缀和的思想，枚举右端点，然后维护的前缀和最小值来得到以为右端点长度大于等于k的连续段数字和最大值。当存在最大值非负的时候表明合法。
时间复杂度
因为只需要维护前缀最小和当前前缀和，所以可以省去前缀和数组的使用，空间复杂度

int solve(int n, int k, vector<int> &a){
    assert(a.size() == n);
    int l = 0, r = 1e9;
    int ans;
    while(l <= r){
        int mid = (r+l)>>1;
        int ps = 0, s = 0, cur = 0;
        for(int i = 0; i < k; ++i)
            if(a[i] >= mid) s ++;
            else s--;
        if(s >= 0){
            ans = mid; l = mid+1; continue;
        }
        int flag = 0;
        for(int i = k; i < n; ++i){
            if(a[i-k] >= mid) cur++;
            else cur--;
            ps = min(ps, cur);
            if(a[i] >= mid) s++;
            else s--;
            if(s-ps >= 0){
                flag = 1; break;
            }
        }
        if(flag) ans = mid, l = mid+1;
        else r = mid-1;
    }return ans;
}