【CQOI2009】中位数

题面

分析

由于是中位数，所以其它数的具体值不需要考虑，我们只需知道其它数与\(b\)的大小关系即可。在一段序列中，要使\(b\)为中位数，则比\(b\)大的数一定和比\(b\)小的数一样多。

于是考虑将比\(b\)大的数记为\(1\)，比\(b\)小的数记为\(-1\)，这样可以利用前缀和与差分，在\(b\)的两端分别找一段连续的序列，如果它们的值为\(0\)，则满足条件。一开始我直接用了\(n^2\)找，这样会t两个点，于是想到桶计数，只用了\(60ms\)。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

int n, b, pos, cnt;
int a[100005], pre[100005], last[100005],ton[100005];

int main() {
    read(n), read(b);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        if (a[i] < b) a[i] = -1;
        else if (a[i] > b) a[i] = 1;
        else if (a[i] == b) pos = i;
    }
    for (int i = pos - 1; i; --i) {
        pre[i] = pre[i + 1] + a[i];
        if (!pre[i]) cnt++;
        ton[-pre[i]]++;
    }
    for (int i = pos + 1; i <= n; ++i) {
        last[i] = last[i - 1] + a[i];
        if (!last[i]) cnt++;
    }
    /*for (int i = pos - 1; i; --i) 这样写会超时
        for (int j = pos + 1; j <= n; ++j)
            if (pre[i] + last[j] == 0)
            cnt++;*/
    for (int i = pos + 1; i <= n; ++i) cnt += ton[last[i]];
    printf("%d", cnt + 1);//加上它本身
    return 0;
}

【CQOI2009】中位数

原文：https://www.cnblogs.com/hlw1/p/11306942.html