hdu 4908 BestCoder Sequence(计数)

题目链接：hdu 4908 BestCoder Sequence

题目大意：给定N和M，N为序列的长度，由1~N组成，求有多少连续的子序列以M为中位数，长度为奇数。

解题思路：v[i]记录的是从1~i这些位置上有多少个数大于M，i-v[i]就是小于M的个数。pos为M在序列中的位置。如果有等式i−j=2∗(v[i]−v[j−1]),i≥pos≥j

那么i和j既是一组满足的情况。将等式变形i−2∗v[i]=j−2∗v[j−1].

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 40000;
int N, M, pos, v[maxn+5], c[2][maxn*2+5];

void init () {
    int a;
    v[0] = 0;

    for (int i = 1; i <= N; i++) {
        v[i] = v[i-1];
        scanf("%d", &a);
        if (a > M)
            v[i]++;
        if (a == M)
            pos = i;
    }
}

int solve () {
    memset(c, 0, sizeof(c));

    for (int i = 1; i <= pos; i++) {
        int tmp = i - 2 * v[i-1];
        c[0][tmp + maxn]++;
    }

    for (int i = pos; i <= N; i++) {
        int tmp = i - 2 * v[i];
        c[1][tmp + maxn]++;
    }

    int ans = 0;
    for (int i = 0; i <= maxn*2; i++)
        ans += c[0][i] * c[1][i];
    return ans;
}

int main () {
    while (scanf("%d%d", &N, &M) == 2) {
        init();
        printf("%d\n", solve());
    }
    return 0;
}