牛客NOIP提高组R1 A中位数(二分)

题意

题目链接

Sol

很神仙的题目啊，考场上只会$n^2$的暴力。。

考虑直接二分一个$mid$，我们来判断最终答案是否可能大于$x$。

判断的时候记录一下前缀最小值即可，

设$s[i]$表示$1-i$中有多少比它大的，要求的长度为$len$，我们记下$s[i - len]$的最小值为$Mi$

若$s[i] - Mi > 0$，那么说明在长度至少为$len$的区间中，大于$mid$的数和小于$mid$的数相互抵消后仍然有比$mid$大的数，此时$mid$是合法的

第一次做这种二分答案，但答案不是给出的数的题。神仙啊qwq

/*

*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<vector>

#include<set>

#include<queue>

#include<cmath>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

#include<set>

#include<vector>

//#define int long long

#define LL long long

//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)

//char buf[(1 << 22)], *p1 = buf, *p2 = buf;

using namespace std;

const int MAXN = 1e5 + , INF = 1e9 + , mod = 1e9 + ;

const double eps = 1e-;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, len, s[MAXN], a[MAXN];

int check(int x) {

    for(int i = ; i <= N; i++)

        if(a[i] < x) s[i] = -;

        else s[i] = ;//s[i] :  1 - i中有多少比x大的

    int Mi = ;

    for(int i = ; i <= N; i++) {

        s[i] += s[i - ];

        if(i >= len) Mi = min(Mi, s[i - len]);

        if(i >= len && (s[i] - Mi > )) return ;

    }

    return ;

}

int main() {

//    freopen("a.in", "r", stdin);

//    freopen("c.out", "w", stdout);

    N = read(); len = read();

    for(int i = ; i <= N; i++) a[i] = read();

    int l = , r = 1e9 + , ans;

    while(l <= r) {

        int mid = l + r >> ;

        if(check(mid)) ans = mid, l = mid + ;//是否有比mid大的解

        else r = mid - ;

    }

    printf("%d", ans);

    return ;

}

/*

5 4

7 2 3 2 6

*/

巴特西

牛客NOIP提高组R1 A中位数(二分)

题意

Sol

最新文章

热门文章